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

public class PermuteString { //Function for swapping the characters at position I with character at position j public static String swapString(String a, int i, int j) { char[] b =a.toCharArray(); char ch; ch = b[i]; b[i] = b[j]; b[j] = ch; return String.valueOf(b); } public static void main(String[] args) { String str = "ABC"; int len = str.length(); System.out.println("All the permutations of the string are: "); generatePermutation(str, 0, len); } //Function for generating different permutations of the string public static void generatePermutation(String str, int start, int end) { //Prints the permutations if (start == end-1) System.out.println(str); else { for (int i = start; i < end; i++) { //Swapping the string by fixing a character str = swapString(str,start,i); //Recursively calling function generatePermutation() for rest of the characters generatePermutation(str,start+1,end); //Backtracking and swapping the characters again. str = swapString(str,start,i); } } } }

Java Program to find all the permutations of a string

Algorithm

All Answers

Program:

Java String Programs

This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now