Q:

Java Program to find all the permutations of a string

belongs to collection: Java String Programs

0

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

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Program:

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);    
            }    
        }    
    }    
}    

Output:

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Java String Programs

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Java Program to remove all the white spaces from a... >>
<< Java Program to find the longest repeating sequenc...