Java Program to find all the permutations of a string

To solve this problem, we need to understand the concept of backtracking.

According to the backtracking algorithm:

  • Fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three strings are formed: ABC, BAC, and CBA by swapping A with A, B and C respectively.
  • Repeat step 1 for the rest of the characters like fixing second character B and so on.
  • Now swap again to go back to the previous position. E.g., from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So, now we got ABC and ACB.
  • Repeat these steps for BAC and CBA, to get all the permutations.
Java Program to find all the permutations of a string

For programming, follow the algorithm given below:

Algorithm

main()

  • STEP 1: START
  • STEP 2: DEFINE string str = “ABC”.
  • STEP 3: len = str.length().
  • STEP 4: PRINT “All the permutations of the string are:”
  • STEP 5:CALL generatePermutation(str, 0, len).
  • STEP 6: END

generatePermutation(String str, int start, int end)

  • STEP 1: START
  • STEP 2: if(start==end-1)
    PRINT str
    else go to STEP 3
  • STEP 3: SET i = start. REPEAT STEP 4 to STEP 7 UNTIL i<end.
  • STEP 4: str = swapstring(str, start, i).
  • STEP 5: generatePermutation(str, start + 1, end).
  • STEP 6: str = swapstring(str, start, i).
  • STEP 7: i=i+1
  • STEP 8: END

swapString(String a, int i, int j)

  • STEP 1: START
  • STEP 2: char[] b = a.toCharArray()
  • STEP 3: DEFINE char ch
  • STEP 4: ch =b[i]
  • STEP 5: b[i] = b[j]
  • STEP 6: b[j] = ch
  • STEP 7: RETURN String.ValueOf(b)
  • STEP 8: END

Program:

  1. public class PermuteString {    
  2.     //Function for swapping the characters at position I with character at position j    
  3.     public static String swapString(String a, int i, int j) {    
  4.         char[] b =a.toCharArray();    
  5.         char ch;    
  6.         ch = b[i];    
  7.         b[i] = b[j];    
  8.         b[j] = ch;    
  9.         return String.valueOf(b);    
  10.     }    
  11.         
  12.     public static void main(String[] args)    
  13.     {    
  14.         String str = “ABC”;    
  15.         int len = str.length();    
  16.         System.out.println(“All the permutations of the string are: “);    
  17.         generatePermutation(str, 0, len);    
  18.     }    
  19.         
  20.     //Function for generating different permutations of the string    
  21.     public static void generatePermutation(String str, int start, int end)    
  22.     {    
  23.         //Prints the permutations    
  24.         if (start == end-1)    
  25.             System.out.println(str);    
  26.         else    
  27.         {    
  28.             for (int i = start; i < end; i++)    
  29.             {    
  30.                 //Swapping the string by fixing a character    
  31.                 str = swapString(str,start,i);    
  32.                 //Recursively calling function generatePermutation() for rest of the characters     
  33.                 generatePermutation(str,start+1,end);    
  34.                 //Backtracking and swapping the characters again.    
  35.                 str = swapString(str,start,i);    
  36.             }    
  37.         }    
  38.     }    
  39. }    

Output:

All the permutations of the string are:
ABC
ACB
BAC
BCA
CBA
CAB

Leave a Comment