Saturday, September 23, 2023

How to Find All Permutations of String in Java using Recursion? Solution Example

How to find all permutations of a String using recursion is one of the tricky coding questions from programming job interviews. I have first seen this question in my college exam when we were asked to code the solution using C or C++ language. Since then I have seen this question many times at various written tests and Java interviews for a junior developer position. It does not only serve as a good question to check whether the candidate understands recursion but also its one of the better java programming exercise for beginners.

Typically, you will be asked to write a method, which accepts a String and print all permutations or may return all permutations in a List for a junior developer position. Depending upon the company you are going for an interview, they may ask you to code on IDE like Eclipse or NetBeans, or simply write code in plain paper, so be prepared for both.

There are two main ways to solve this problem, using loops or by using recursion, the second one is what the interviewer expects. 

Since recursion is a tricky programming concept to master, it's not easy for every programmer to solve this problem on the fly, especially if you are not coding on a daily basis or don't have that highly sought-after code sense.




Solution 1 - Final All Permutations of given String Using Recursion and Loop

Now let's get back to the problem, Permutation refers to the ordering of characters but it takes position into account i.e. if you have String "ab" then it will have just 2 permutations "ab" and "ba", because the position of the character in both Strings is different.

Similarly for a String of n characters there are !n (factorial of n) permutations are possible e.g. for a String of 3 characters like "xyz" has 6 possible permutations, xyz, xzy, yxz, yzx, zxy, zyx as seen in our example. 

As I told you there are two ways to solve this problem either by using for loop (iterative algorithm) or by using recursion, but the most elegant solution is a combination of both loop and recursion.



If you remember the factorial problem you know that factorial is naturally recursive i.e. factorial of n is nothing but n * factorial of n -1. Similarly, permutations are also a recursive problem e.g. permutation of n characters is nothing but fixing one character and calculating permutation of n - 1 characters e.g. in the case of "xyz", you can fix "x" and calculate permutation of "yz".

In order to calculate all permutations of a String, you need to repeat this exercise for all characters one at a time. This is where for loop comes into the picture. So, this solution uses both for loop and recursion to print all permutations of a given String.

In the case of recursion, the most important question is the base case, because that is responsible for stopping recursive calls. If you don't have a base case then your program will eventually terminate with java.lang.StackOverFlowError.

In this problem, our base case is a permutation of empty String, which is nothing but the empty String itself. After each call, the problem set is reduced and inches towards the base case, when it reaches there stack starts rolling down and calculates the result.





Java Program to Print All Permutation of a String

Here is our sample Java program to print all permutations of a given string using a recursive algorithm. It uses both loop and a recursive call to solve this problem. It also demonstrates a technique of hiding your implementation detail using a private method and exposing a much cleaner public method as API. In our solution, we have two permutation methods, one is public, and the other is private.

The first method is clean and exposed to the client but the second method requires you to pass an empty string as the initial value of the perm parameter which is used to store the intermediate permutation of String.

If you expose this method to the client then it will wonder about this empty String, since it's part of the implementation, it's better to hide and get rid of it as soon as you have a better algorithm to solve this problem, how about taking it as an exercise?

/**
  * Java program to find all permutations of a given String using recursion. 
  * For example, given a String "XYZ", this program will print 
  * all 6 possible permutations of
  * input e.g. XYZ, XZY, YXZ, YZX, ZXY, XYX
  *
  * @author Javin Paul
  */
public class StringPermutations {

    public static void main(String args[]) {
        permutation("123");
    }

   
 /*
  * A method exposed to client to calculate permutation of String in Java. 
  */
   public static void permutation(String input){
          permutation("", input);
   }

   /*
    * Recursive method which actually prints all permutations
    * of given String, but since we are passing an empty String
    * as current permutation to start with,
    * I have made this method private and didn't exposed it to client. 
    */
   private static void permutation(String perm, String word) {
        if (word.isEmpty()) {
            System.err.println(perm + word);

        } else {
            for (int i = 0; i < word.length(); i++) {
                permutation(perm + word.charAt(i), word.substring(0, i) 
                                + word.substring(i + 1, word.length()));
            }
        }

    }
}

Output:
123
132
213
231
312
321


Like everything else, practice is your friend, doing this kind of coding exercise on a daily basis, solving programming puzzles, and doing more complex programs available on internet sites like project Euler, TopCoder will help you to build confidence in your coding and problem-solving skill.

You can also take the help of some classic coding interview courses and books like Cracking the Coding interview to do well on coding interviews

Java Program to find all permutation of String





Explanation of Code :

All code for calculating permutation of String is inside permutation(String perm, String word)  method, I have purposefully made this method private because of additional parameter I am passing as an initial value of permutation.

This demonstrates a technique of hiding implementation detail from a client and exposing a much cleaner API to the client e.g. just permutation(String input)  method, passing empty String is an implementation detail and ugly for a client to pass whenever it needs to calculate permutation. It is also an exercise for you to see if you can improve the code by getting rid of that empty String.

The algorithm is nothing but keeping one character fix and then calculating permutations of others. The crux of the program is in the following code segment :

 for (int i = 0; i < word.length(); i++) {
   permutation(perm + word.charAt(i), word.substring(0, i) 
                    + word.substring(i + 1, word.length()));
}


Here we have a for loop to go through each character of String e.g. for input "123" this loop will run three times. In each iteration, we are making a recursive call to function itself i.e. permutation(String perm, String word)  method, where the first parameter is used to store the result.


After 1st iteration perm (first parameter of permutation() method) will be "" + 1 as we are doing word.charAt(i) and i is zero. Next, we take out that character and pass the remaining characters to the permutation method again e.g. "23" in the first iteration. 

The recursive call ends when it reaches to base case i.e. when the remaining word becomes empty, at that point "perm" parameter contains a valid permutation to be printed. You can also store it into a List if you want to.

Here is a nice diagram that visually shows what this algorithm does :

Print all permutation of a String in Java example



That's all on how to find all permutations of a String in Java using recursion. It's a very good exercise for preparing Java coding interviews. Why not you give it a try and come up with another solution? also could you calculate the complexity of this algorithm, to it looks n*!n because the loop will run for n times, and for each n, we will call the permutation method. 

Also, how about writing some JUnit test cases to see if this solution works for various inputs e.g. empty String, one letter String, many letters String, String with duplicate characters, etc? It's a good practice to become hands-on in writing JUnit tests.


If you are interested in more of such coding questions, you can check the following interview questions collected from various Java interviews :
  • 20 String based Coding Problems from Java Interviews [solution]
  • 30 Array-based Coding Questions from Java Interviews [solution]
  • How to check if two String are an anagram of each other? [solution]
  • How to find duplicate words in a given String? [solution]
  • How to check if the given String is Palindrome in Java? [solution]
  • How to print first not repeated character from given String in Java? [solution]
  • How to reverse String in Java without using recursion? [solution]
  • How to count the occurrence of a given character in String? [solution]
And, now is the quiz time, which one is your favorite string based coding problems? counting occurance of characters, palindrom, reverse a String, finding duplicates or this one?

28 comments:

  1. Thanks for the wonderful program. Also I have seen program which asks to print only the forward direction permutation.
    Example: Input: XYZ
    Output: X, XY, XZ, Y, YZ, Z, XYZ
    Can you please help?

    ReplyDelete
  2. @Roy

    Check this code:
    private static void permutation(String perm, String word) {
    if (word.isEmpty()) {
    System.err.println(perm + word);

    } else {
    for (int noMore = 0; noMore <= 1; noMore++) {
    if (noMore == 0) {
    for (int i = 0; i < word.length(); i++) {
    permutation(perm + word.charAt(i), word.substring(i + 1, word.length()));
    }
    } else {
    permutation(perm, "");
    }
    }
    }
    }

    ReplyDelete
  3. How do you calculate time complexity of this solution? For a String of n characters, what would be complexity O(n^2)? Since program is using both looping and recursion, its difficult to calculate time complexity.

    ReplyDelete
  4. Instead of printing Perm+word, only printing Perm is sufficient coz word is empty when we print the result.

    ReplyDelete
  5. This program not work correctly if in case there are repeating numbers

    ReplyDelete
  6. Thanks for the wonderful code. i edited to work it for repetition.

    This would work for repetition.

    import java.util.*;


    class StringPermutation
    {
    public static void main(String[] args) {
    String str;
    Scanner sc = new Scanner(System.in);
    str=sc.next();
    permutation("",str);
    }

    public static void permutation(String fixed,String sub)
    {
    if(sub.equals(""))
    {
    System.out.println(fixed);
    }
    else
    {
    int a[] = new int[256];
    for(int i=0;i<sub.length();i++)
    {
    if(a[(int)sub.charAt(i)]==0)
    {
    a[(int)sub.charAt(i)]=1;
    permutation((fixed+sub.charAt(i)),sub.substring(0,i)+sub.substring(i+1,sub.length()));
    }
    }
    }
    }
    }

    ReplyDelete
  7. not getting why you use system.err.println(), why you dont use System.out.println() here.

    ReplyDelete
    Replies
    1. System.err.println() gives statement in red color

      Delete
  8. How can I count number of possible outcomes and display it in this existing code?
    e.g. for "abc" display total count as 6 in the output along with the possible combinations.

    ReplyDelete
  9. how would one write this code without using a method, only nested loops?

    ReplyDelete
  10. Hi Please find my approach to solve this problem:

    public static void main(String[] args) {
    printPermutationStrings("abcde");
    }

    static void printPermutationStrings(String str){
    printPermutationStrings("abcde", "");
    }


    static void printPermutationStrings(String str, String prefix){
    if(str == null || str.length() < 2){
    return;
    }

    if(str.length() == 2){
    System.out.println(prefix + str);
    System.out.println(prefix + new StringBuffer(str).reverse().toString());
    }

    for(int i=0; i < str.length(); i++){
    char c = str.charAt(i);
    String s2 = "";
    for(int j = 0; j < str.length(); j++){
    if(i != j){
    s2 += str.charAt(j);
    }
    }
    printPermutationStrings(s2, prefix + c);
    }

    }

    ReplyDelete
  11. Some bad html markup inserted into your code, specifically for the "less than" character in the for loop.

    ReplyDelete
  12. Thank you @Anonymous, I'll correct it.

    ReplyDelete

  13. @author Javin Paul
    // above code has some corrections
    //now i have corrected it


    /**
    * Java program to find all permutations of a given String using recursion.
    * For example, given a String "XYZ", this program will print all 6 possible permutations of
    * input e.g. XYZ, XZY, YXZ, YZX, ZXY, XYX
    *
    * @author Javin Paul
    */
    public class StringPermutations {

    public static void main(String args[]) {
    permutation("123");
    }


    /*
    * A method exposed to client to calculate permutation of String in Java.
    */
    public static void permutation(String input){
    permutation("", input);
    }

    /*
    * Recursive method which actually prints all permutations
    * of given String, but since we are passing an empty String
    * as current permutation to start with,
    * I have made this method private and didn't exposed it to client.
    */
    private static void permutation(String perm, String word) {
    if (word.isEmpty()) {
    System.err.println(perm + word);

    } else {
    for (int i = 0; i < word.length(); i++) {
    permutation(perm + word.charAt(i), word.substring(0, i)
    + word.substring(i + 1));
    }
    }

    }
    }

    /*Output:
    123
    132
    213
    231
    312
    321
    */

    ReplyDelete
  14. @author Javin Paul

    could u do me a favour
    plzz upload the code of finding the permutation of a String where in output repetitions are not allowed without using Collection

    Example
    input - AAB
    output -
    AAB
    ABA
    BAA

    LIKE THIS

    ReplyDelete
  15. Hello @Ankit, how different is your problem from the one in this article, to me it looks similar ..

    ReplyDelete
  16. Plzz help with this code How to sort the sentence according to the length of the word

    ReplyDelete
  17. #Simplest Code I guess :

    public class StringQuestion
    {
    public static void main(String args[])
    {
    String string="abcd";
    char[] str=string.toCharArray();
    for(int i=0;i<str.length;i++)
    {

    for(int j=0;j<str.length;j++)
    {
    System.out.println(str[j]+""+str[(j+1)%4]+""+str[(j+2)%4]+""+str[(j+3)%4]);
    }
    char temp=str[i];
    str[i]=str[str.length-i-1];
    str[str.length-i-1]=temp;
    }

    }
    }

    ReplyDelete
  18. Added code to avoid duplicate entries..

    public class Test {

    public static void main(String args[]) {

    permutation("Apl");
    System.out.println(set);

    }

    public static void permutation(String input) {

    permutation("", input);
    }

    private static SortedSet set = new TreeSet();

    private static void permutation(String perm, String word) {

    if (word.isEmpty()) {
    String setString = perm + word;
    set.add(setString);
    } else {
    for (int i = 0; i < word.length(); i++) {
    permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1, word.length()));
    }
    }
    }
    }

    ReplyDelete
  19. public class Test {

    public static void main(String args[]) {

    permutation("Apl");
    System.out.println(set);

    }

    public static void permutation(String input) {

    permutation("", input);
    }

    private static SortedSet set = new TreeSet();

    private static void permutation(String perm, String word) {

    if (word.isEmpty()) {
    String setString = perm + word;
    set.add(setString);
    } else {
    for (int i = 0; i < word.length(); i++) {
    permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1, word.length()));
    }
    }
    }
    }

    ReplyDelete
  20. @Ankit can u solve your problem ? i need that code :D

    "Ankit Kannaujia said...

    @author Javin Paul

    could u do me a favour
    plzz upload the code of finding the permutation of a String where in output repetitions are not allowed without using Collection

    Example
    input - AAB
    output -
    AAB
    ABA
    BAA

    LIKE THIS

    Read more: http://javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html#ixzz5DVT3bywX
    "

    ReplyDelete
  21. CAn anyone please do this iteration once I'm not getting it

    ReplyDelete
  22. Can anyone please do this program iteration once i'm not getting after first first iteration "abc"

    ReplyDelete
  23. let a = "abc";

    function permute(perm, word) {
    if(word.length === 0) {
    console.log(perm+word);
    } else {
    for(let i=0; i < word.length; i++) {
    permute(perm+word.charAt(i),
    word.substring(0, i)+ word.substring(i+1, word.length));
    }
    }
    }

    permute("", a);

    console.log("Using Fixed approach now")
    // Second approach, using fixed pos
    function swap(word, i, j) {
    let c = word.split('');
    let t = c[i];
    c[i] = c[j];
    c[j] = t;
    return c.join();
    }
    function permute1(word, s, e) {
    if(s == e) {
    console.log(word);
    } else {
    for(let i=s; i < e; i++) {
    word = swap(word, s, i);
    permute1(word, s+1, e);
    word = swap(word, s, i);
    }
    }
    }
    permute(a, 0, a.length);

    permute("", a);

    ReplyDelete
  24. Your code is incorrect and goes out of range of array, the correct code is:

    private static void permutation(String perm, String word)
    {
    if (word.isEmpty())
    {
    System.err.println(perm + word);
    }
    else
    {
    for (int i = 0; i < word.length(); i++)
    {
    permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1,
    word.substring(i + 1).length()));
    }
    }
    }

    Read more: https://javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html#ixzz6BeOCUSA9

    ReplyDelete
  25. this cade give duplicate value if there is deplucate letters. for ABCD permutation is 4! = 24, for AABC it should be 4!/2! = 12

    ReplyDelete