Problem
Write a method to compute all permutations of a string.
Example
For a string of length n, there are n! permutations.
INPUT: “abc”
OUTPUT: “abc” “acb” “bac” “bca” “cab” “cba”
So, we have 3! = 6 items for string abc.
Solution
There are several ways to do this. Common methods use recursion, memoization, or dynamic programming.
The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)
Lets split up the problem in 2 cases - when duplicates are not allowed and when allowed.
Case 1 : If String has “NO” duplicate
Method 1 - Recursion
Answer: Here is a recursive solution to print all the permutations of a string.
The idea is to keep the first character constant and generate permutations with the rest. Then keep the first two characters constant and generate permutations with the rest until you are out of characters.
So for string “abc”, the idea is that the permutations of string abc are a + permutations of string bc, b + permutations of string ac and so on.
The following piece of a code is a very efficient use of recursion to find the possible permutation of a string.
Caution : However, this solution does not take care of duplicates. It is assumed that there are no duplicates in the string.
public class Permutations {
public static void permutate(String s) { permutateHelper("", s); }
//Helper function
private static void permutateHelper(String prefix, String rest) {
int N = rest.length();
if (N == 0)
System.out.println(prefix);
else {
for(int i = 0; i < N; i++){
perm1(prefix + rest.charAt(i), rest.substring(0, i)
+ rest.substring(i+1, N));
}
}
}
public static void main(String\[\] args) {
String alphabet = "Testt";
String elements = alphabet.substring(0, alphabet.length());
perm1(elements);
}
}
Dry running the code---ABC A---BC AB---C ABC--- -------------------------------ABC AC---B ACB--- -------------------------------ACB B---AC BA---C BAC--- -------------------------------BAC BC---A BCA--- -------------------------------BCA C---AB CA---B CAB--- -------------------------------CAB CB---A CBA--- -------------------------------CBA
Method 1b) Recursion and Backtracking
This will also not work for duplicates. I left out the implementation of the swap method since that implementation is not important here.
//actual helper function
void permutateHelper( char\[\] str, int index )
{
int i = 0;
if( index == strlen(str) )
{ // We have a permutation so print it
printf(str);
return;
}
for( i = index; i < strlen(str); i++ )
{
swap( str\[index\], str\[i\] ); // It doesn't matter how you swap.
permutateHelper( str, index + 1 );
swap( str\[index\], str\[i\] );
}
}
//actual function
public static void permutate( char\[\] str ){
permutateHelper (str, 0);
}
//calling the function
permutate("abcdefgh".toCharArray());
Case 2 : If String has duplicate
What do we do if there are duplicates in the string?
Solution 1:
The trick is to sort the characters in the alphabetical order first. We can then ignore the duplicates easily when generate the permutation.
Solution 2
void permutateHelperDuplicate(String prefix, String rest){
int N = 0;
if(rest!=null)
N = rest.length();
if (N==0)
{
System.out.println(prefix);
}
else
{
for (int i = 0; i < rest.length(); i++)
{
//test if rest\[i\] is unique.
boolean found = false;
for (int j = 0; j < i; j++)
{
if (rest.charAt(j) == rest.charAt(i)) //rest\[j\]==rest\[i\]
found = true;
}
if(found)
continue;
String newPrefix = prefix + rest.charAt(i);
String newRest = rest.substring(0, i) + rest.substring(i+1,N);
permutateHelperDuplicate(newPrefix, newRest);
}
}
}
**Method 3 - Use HashSet **
In this method, we can have an hashset of string, and once we generate the permutation, we add it to hashset if it is not there, otherwise we ignore it.
Please let me know if you any suggestions.