Finding all permutations of a String in Java

There are many ways of finding the permutations of a string . From the mathematics point of view there can be n! permutations where n is number of  character in the string.

Solution1  :

Use recursion.

• Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
• The base case is when the input is an empty string the only permutation is the empty string.

       

public static void perm(String s){

  if(s ==null || s.isEmpty()){

         return;

       }

perm("", s);

}


public static void perm(String prefix , String s){

     if(s.length() == 0){

        System.out.println(prefix);

      } else {

   int stringLength = s.length();

   for (int i = 0; i < stringLength; i++) {

   perm(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1));

    }

}

}

public static void main(String[] args){

  perm("abc");

}
output : 

abc

acb

bac

bca

cab

cba

Time Complexity would be : O(n*n!) as for each element you required n-1 permutations of the 

string so overall n! permutations.




Space complexity would be : O(n)



Note 2: Time taken to execute the method for various length of string:







for n=10 and 10!=3628800 number and total time taken to complete the output is = 93.31 sec

for n=9 and 9!=362880 number and total time taken to complete the output is = 6.312 sec

for n=8 and 8!=40320 number and total time taken to complete the output is = 365 ms

for n=7 and 7!=5040 number and total time taken to complete the output is = 92 ms

for n=6 and 6!=720 number and total time taken to complete the output is = 43 ms

for n=5 and 5!=120 number and total time taken to complete the output is =4 ms

for n=4 and 4!=24 number and total time taken to complete the output is = 1 ms

for n=3 and 3!=6 number and total time taken to complete the output is = 1 ms

for n=2 and 2!=2 number and total time taken to complete the output is = 0 ms

Solution2 :

Use recursion and swapping.

• Try each of the index in turn as the current index and then find all the permutations of the remaining letters using a recursive call and swapping the element to the current index.
• The base case is when the input  is an 0 index the only permutation is the permutated string.

private static void doPerm(StringBuffer str, int index){
     if(index <= 0)

         System.out.println(str);           

     else { 

      int n = str.length();

         int currPos = n-index;


doPerm(str, index-1);
         for (int i = currPos+1; i < n; i++) {

             swap(str,currPos, i);

             doPerm(str, index-1);

             swap(str,i, currPos);


         }
     }

 }

private  static void swap(StringBuffer str, int pos1, int pos2){


     char t1 = str.charAt(pos1);

     str.setCharAt(pos1, str.charAt(pos2));

}


public static void main(String[] args){
  long start = System.currentTimeMillis();

  String str = "abcd";

  StringBuffer strBuf = new StringBuffer(str);

         doPerm(strBuf,str.length());

  long end = System.currentTimeMillis();

  System.out.println("total time taken=" + (end -start)  +  " ms");

 }





Time Complexity would be : O(n*n!) as for each element you required n-1 permutations of the 
string so overall n! permutations.But the use of String buffer and in memory swapping 

the elements reduces the execution time. 





Space complexity would be : O(n)



Note 2: Time taken to execute the method for various length of string:







for n=10 and 10!=3628800 number and total time taken to complete the output is = 33.31 sec

for n=9 and 9!=362880 number and total time taken to complete the output is = 3.312 sec

for n=8 and 8!=40320 number and total time taken to complete the output is = 185 ms

for n=7 and 7!=5040 number and total time taken to complete the output is = 42 ms

for n=6 and 6!=720 number and total time taken to complete the output is = 13 ms

for n=5 and 5!=120 number and total time taken to complete the output is =4 ms

for n=4 and 4!=24 number and total time taken to complete the output is = 1 ms

for n=3 and 3!=6 number and total time taken to complete the output is = 1 ms

for n=2 and 2!=2 number and total time taken to complete the output is = 0 ms





This solution is seems to be more  optimal solution as compare to solution 1.So 
highly recommended. 

solution 1 & solution 2 are taking same time upto 5 elements in the string but as we grow larger say upto 10 characters , solution 2 fit the most with respect to the time complexity and taking 1/3rd time as compare to solution1. It uses the technique to swap the elements in memory and use of string buffer reduces the time.



Solution 2 is highly recommended for finding the permutations of the string.

Two solutions are being mentioned and compare with the time . Clearly 2nd solution is much more optimal solution and its uses in memory swapping the element and making permutation of the other string excluding the current index character. Above two solutions gives all the permutations of a string while to remove the duplicates output need to be write in a Set to avoid any duplicates.

Solution 3 without recursions and without duplicates :  

      

public static Set<String> generatePermutation(String input){

  Set<String> set = new HashSet<String>();

  if(input == null){ return null; }

  if (input == "") {return set;}

  Character a = input.charAt(0);

  if (input.length() > 1){

   input = input.substring(1);

   Set<String> permSet = generatePermutation(input);

   for (String x : permSet){

    for (int i = 0; i <= x.length(); i++) {

     set.add(x.substring(0, i) + a + x.substring(i));

    }

   }

  } else {

   set.add(a + "");

  }

  return set;

 }

public static void main(String[] args){

  long start = System.currentTimeMillis();

  String str = "AACC";

  System.out.println(generatePermutation(str));

  long end = System.currentTimeMillis();

  System.out.println("total time taken=" + (end -start)  +  " ms");

 }
Output : 



[CACA, ACAC, ACCA, AACC, CCAA, CAAC]

total time taken=1 ms
Note : No duplicates are in the output and this is the most optimal solution for 

finding the permutations  of a string.       
 

Enjoy coding and enjoy Java!!!!!