Java Program to Print Permutations of String

A string is given and you need to print all the possible ways for that string. Permutation is arranging the characters of a string to get outputs from the given string.

For example let ‘rat’ be the string and the list of all possible permutations for string are:

1. rat
2. art
3. tar
4. rta
5. tra
6. atr

In order to solve these type of problems first we need to learn backtracking algorithm.

Backtracking Algorithm

Algorithm

1.Establish a string.

2.Fix one character, then switch the others.

3.For the remaining characters, call permutationFunction().

4.Go back and switch the characters once again.

Procedure

1. Replace the rest of the characters with the character in the first position after fixing the first character. Similar to ABC, the first iteration results in the formation of three strings: ABC, BAC, and CBA by replacing A with A, B, and C, respectively. For the remaining characters, repeat step 1 by fixing the second character B and so forth.
2. Switch again to return to your original position. For instance, starting with ABC, we would create ABC by adjusting B once more before going back and switching B and C. We now have ABC and ACB.
3. Repeat these processes for BAC and CBA to obtain all possible combinations.

If repetition is allowed we can use recursion method to get the output

Repetition- Repeating same strings in the output

Recursion Method 1

In this method the function is called recursively until the string passed gets empty (termination condition). Using this method we will get repeated permutations of the string.

Java program to print all the permutations of the given string

public class Main {
static void printStrings(String str, String ans)
{
// If string is empty
if (str.length() == 0) {
System.out.println(ans + " ");
return;
}
for (int i = 0; i < str.length(); i++) {

char ch = str.charAt(i);
String ros = str.substring(0, i) +str.substring(i + 1);
// Calling the function recursively
printStrings(ros, ans + ch);
}
}// printStrings
//Main method
public static void main(String[] args)
{
String s = "abb";
printStrings(s, "");
} 
}//main

Output

Explanation

In the program above, we are calling the function called "printStrings" with the string "abb" and we are supplying another empty string as a parameter to append the string's remaining characters. The function ends by producing an empty string as output and the programme is ended if the string is empty. Using a for loop, we will go through the string, adding each additional character apart from the one at position I and calling the function repeatedly until the string is empty.

Recursion Method 2

To avoid the repetitions of the string we will use another recursion method.

Program to print all different permutations of string

// Java program to print all the permutations of the given string
public class Main {
    static void Permutations(String s1,String ans)
    {
        if (s1.length() == 0) {
            System.out.println(ans + " ");
            return;
        }
        boolean a[] = new boolean[26];
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            String ros = s1.substring(0, i) +s1.substring(i + 1);
            if (a[c - 'a'] == false)
                Permutations(ros, ans + c);
            a[c- 'a'] = true;
        }
    }
    public static void main(String[] args)
    {
        String s = "java";
        Permutations(s,"");
    }
}

Output

Explanation

Make a 26-character long Boolean array that tracks the character being used. The recursive call will be made if the character hasn't been utilised. If not, don't place any calls. When the given string is empty, the sentence will end.

3.Iterative Approach: Using Collection

import java.util.ArrayList;
import java.util.List;
 
class Main
{
    public static void Permutations(String s)
    {
        if (s == null || s.length() == 0) 
        {
            return;
        }
        List<String> result = new ArrayList<>();
        result.add(String.valueOf(s.charAt(0)));
        for (int i = 1; i < s.length(); i++)
        {
            for (int j = result.size() - 1; j >= 0 ; j--)
            {
                String s1 = result.remove(j);
                for (int k = 0; k <= s1.length(); k++)
                {
                    result.add(s1.substring(0, k) + s.charAt(i) + s1.substring(k));
                }
            }
        }
        System.out.println(result);
    }
    public static void main(String[] args)
    {
        String string = "QWE";
        Permutations(string);
    }
}

Output