Java Program to find all the permutations of a string

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.

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:

Output:

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