Print all possible permutations of a String – Recursive Method

Find all possible permutations of a String is one of the most common question that is asked if you are appearing for any good company. Although I am gonna discuss the Java programs here but you can use the same logic and can code in any programming language whether it is C, C#, C++, php or any other language.

– What is Permutation?

-Permutation(a mathematical term) is an act of rearranging elements of a Set( String in this case) in a particular sequence or order. In a set of n elements, maximum possible number of permutations are n!.

For eg- For a Set(or String ) {‘A’, ‘B’,’C’} all possible permutations are –
ABC, ACB, BAC, BCA, CAB, CBA

Jump to programs

1. Permutations with repetition
2. Permutation without repeating output
3. Permutation without repeating output – Best Performance(Recommended)

There are many possible ways to find out the permutations of a String and I am gonna discuss few programs to do the same thing. All the solutions are almost similar except in one case i.e. if one or more characters are appearing more than once then how to process them(i.e. whether to repeat the same output or not). Then I will discuss a method to improve the performance in case if character repeats. So lets start with the very basic one.

1st program – Prints the repeated permutations also

In this we print all the permutations either even if it is repeating as we are not using any check for that.

public class StringPermutationExample {

	public static void main(String[] args) {
		StringBuilder input = new StringBuilder("aaa");
		StringBuilder input2 = new StringBuilder("aab");
		StringBuilder input3 = new StringBuilder("abc");

		permute(input, 0, input.length());
		System.out.println("
");
		permute(input2, 0, input2.length());
		System.out.println("
");
		permute(input3, 0, input3.length());
		System.out.println("
");
	}

	static void exchange(StringBuilder input, int i, int j) {
		String temp;
		temp = input.substring(i, i + 1);
		input.replace(i, i + 1, input.substring(j, j + 1));
		input.replace(j, j + 1, temp);
	}

	static void permute(StringBuilder input, int i, int length) {
		if (i == length - 1) {
			System.out.print(input.toString() + ",");
		} else {
			for (int j = i; j < length; ++j) {
				exchange(input, i, j);
				permute(input, i + 1, length);
				exchange(input, i, j);
			}
		}
	}
}

Output:-
aaa, aaa, aaa, aaa, aaa, aaa, 

aab, aba, aab, aba, baa, baa, 

abc, acb, bac, bca, cba, cab, 

In the above example you can see that results are repeating. In example of ‘aaa’ it is repeating it 6 times. Now lets see how to remove these repeated inputs.

2nd Program – Prints only different strings

In this we print only those Strings which are different. We achieve this by introducing java.util.Set as it ensures that no element in a set could be duplicate. So even if we try to add a duplicate element in this Set it will simply discard it and in the end we will be left with only different String permutations.

import java.util.HashSet;
import java.util.Set;

public class StringPermutationExample {

	public static void main(String[] args) {
		StringBuilder string = new StringBuilder("aaa");
		StringBuilder string2 = new StringBuilder("aab");
		StringBuilder string3 = new StringBuilder("abc");

		Set<String> set = new HashSet<>();

		//permuting and printing first String
		perm(string, 0, string.length(), set);
		System.out.println(set);
		set.clear();

		//permuting and printing second String
		perm(string2, 0, string2.length(), set);
		System.out.println(set);
		set.clear();

		//permuting and printing third String
		perm(string3, 0, string3.length(), set);
		System.out.println(set);
	}

	static void exchange(StringBuilder input, int i, int j) {
		String temp;
		temp = input.substring(i, i + 1);
		input.replace(i, i + 1, input.substring(j, j + 1));
		input.replace(j, j + 1, temp);
	}

	static void perm(StringBuilder input, int i, int length, Set<String> set) {
		if (i == length - 1) {
			set.add(input.toString());
		} else {
			for (int j = i; j < length; ++j) {
				exchange(input, i, j);
				perm(input, i + 1, length, set);
				exchange(input, i, j);
			}
		}
	}
}

Output:-
[aaa]
[aba, aab, baa]
[cab, abc, cba, bca, bac, acb] 

In the above example we can see that how by introducing sets we are able to remove duplicate Strings.

Okk it is a Solution, But is this an optimal solution? No, because although we are avoiding duplicate entries but still we are iterating over every character and we are still finding n! outputs and this is gonna take much extra resources and time in case our Strings are big and have multiple characters repeating multiple times(eg – aaaaabbbbbccccc). So lets see next example on how to improve the performance.

3rd Program – Prints only different strings with Improved Efficiency

This one is the simplest and the most efficient program for the String permutation. In this program we will treat only different characters i.e. if any character is repeating again in the specified String we will simply skip it and by this method we ensure that all the similar characters are skipped except once( at its last occurrence). So lets see the program.

import java.util.HashSet;
import java.util.Set;

public class StringPermutationExample {

	public static void main(String[] args) {
		String input = "aaa";
		String input2 = "aab";
		String input3 = "abc";

		Set<String> set = new HashSet<>();

		permutation(input, "", set);
		System.out.println(set);
		set.clear();

		permutation(input2, "", set);
		System.out.println(set);
		set.clear();

		permutation(input3, "", set);
		System.out.println(set);
	}

	private static void permutation(String input, String sofar, Set<String> set) {
		if (input.equals("")) {
			set.add(sofar);
		}
		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
			if (input.indexOf(c, i + 1) != -1)
				continue;
			permutation(input.substring(0, i) + input.substring(i + 1), sofar + c, set);
		}
	}

}

Output:-
[aaa]
[aba, aab, baa]
[cab, abc, cba, bca, bac, acb] 

Although the output of both the last program is same but the performance of last program is far far better than the second example. Click here to see the chart that shows the difference between the two.

Recommended -