All permutations of a string - PrismoSkills
static void permute(char[] s, int i)
{
if (i==s.length-1)
{
count++; // count no of words output and print the permutation.
System.out.println(count + ") " + new String(s));
return;
}
int curr = i;
for (; i<s.length; i++)
{
swap (s, i, curr);
permute (s, curr+1);
swap (s, i, curr);
}
}
Code to handle duplicate characters
To handle duplicate characters, we need to use a hash-set which will make sure a character already used in an index does not come there again.
This code works for non-repeated characters too.
void permute(char[] s, int i)
{
if (i==s.length-1)
{
count++;
System.out.println(count + ") " + new String(s));
return;
}
HashSet<Character> charsDone =
new HashSet<Character> (); // <== initialize a hash-set at each recursion level
int curr = i;
for (; i<s.length; i++)
{
if (charsDone.contains(s[i])) // <== if char is used, do not re-process it
continue;
charsDone.add(s[i]);
swap (s, i, curr);
permute (s, curr+1);
swap (s, i, curr);
}
}
http://www.geeksforgeeks.org/permutations-string-using-iteration/
http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
permute(str, 0, n-1);
http://www.geeksforgeeks.org/permutations-of-a-given-string-using-stl/
We can use next_permute() that modifies a string so that it stores lexicographically next permutation. If current string is lexicographically largest, i.e., “CBA”, then next_permute() returns false.
Read full article from All permutations of a string - PrismoSkills
static void permute(char[] s, int i)
{
if (i==s.length-1)
{
count++; // count no of words output and print the permutation.
System.out.println(count + ") " + new String(s));
return;
}
int curr = i;
for (; i<s.length; i++)
{
swap (s, i, curr);
permute (s, curr+1);
swap (s, i, curr);
}
}
Code to handle duplicate characters
To handle duplicate characters, we need to use a hash-set which will make sure a character already used in an index does not come there again.
This code works for non-repeated characters too.
{
if (i==s.length-1)
{
count++;
System.out.println(count + ") " + new String(s));
return;
}
HashSet<Character> charsDone =
new HashSet<Character> (); // <== initialize a hash-set at each recursion level
int curr = i;
for (; i<s.length; i++)
{
if (charsDone.contains(s[i])) // <== if char is used, do not re-process it
continue;
charsDone.add(s[i]);
swap (s, i, curr);
permute (s, curr+1);
swap (s, i, curr);
}
}
http://www.geeksforgeeks.org/permutations-string-using-iteration/
Recursion is always costly and iteration is preferred. Below are steps of iterative approach.
- Find no of permutations of the string by calculating value of n!. Then use this value to iterate.
- Store the original string in an auxiliary string and use that string to do the math.
- Fix the first position(character), and swap all the j’th and (j+1)’th characters till (n-1)!.
- At the end of first (n-1)! all the (n-1)th characters will be permuted.
- Now again store the original string to the auxiliary string and swap i’th and (i+1)’th characters and repeat the 3rd and 4th process.
Concept Used : We keep swapping a character only till it reaches the end
- Fix ‘a’. Swap ‘b’ with its next neighbors till b reaches the end.
( “acbd”, “acdb”) - Now ‘c’ will be at the 2nd position, do the same thing with it.
( “adcb”, “adbc”) - Now ‘d’ will be at the 2nd position, do the same thing with it.
( “abdc”, “abcd”) - All 6 i.e., (4!/4)permutations of the first cycle obtained.
- Repeat the above process by bringing swapping ‘a’ with ‘b’
- The new string to “play” will be “bacd”.
int fact(int n){ return (n==1)? 1 : n*fact(n-1);}void printPermutation(string s){ // Find length of string and factorial of length int n = s.length(); int fc = fact(n); // Point j to the 2nd position int j = 1; // To store position of character to be fixed next. // m is used as in index in s[]. int m = 0; // Iterate while permutation count is // smaller than n! which fc for (int perm_c = 0; perm_c < fc; ) { // Store perm as current permutation string perm = s; // Fix the first position and iterate (n-1) // characters upto (n-1)! // k is number of iterations for current first // character. int k = 0; while (k != fc/n) { // Swap jth value till it reaches the end position while (j != n-1) { // Print current permutation cout << perm << "\n"; // Swap perm[j] with next character swap(perm[j], perm[j+1]); // Increment count of permutations for this // cycle. k++; // Increment permutation count perm_c++; // Increment 'j' to swap with next character j++; } // Again point j to the 2nd position j = 1; } // Move to next character to be fixed in s[] m++; // If all characters have been placed at if (m == n) break; // Move next character to first position swap(s[0], s[m]); }}
Algorithm Paradigm: Backtracking
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.
/* Function to swap values at two pointers */void swap(char *x, char *y){ char temp; temp = *x; *x = *y; *y = temp;}/* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */void permute(char *a, int l, int r){ int i; if (l == r) printf("%s\n", a); else { for (i = l; i <= r; i++) { swap((a+l), (a+i)); permute(a, l+1, r); swap((a+l), (a+i)); //backtrack } }}http://www.geeksforgeeks.org/permutations-of-a-given-string-using-stl/
void permute(string str, string out){ // When size of str becomes 0, out has a // permutation (length of out is n) if (str.size() == 0) { cout << out << endl; return; } // One be one move all characters at // the beginning of out (or result) for (int i = 0; i < str.size(); i++) { // Remove first character from str and // add it to out permute(str.substr(1), out + str[0]); // Rotate string in a way second character // moves to the beginning. rotate(str.begin(), str.begin() + 1, str.end()); }}We can use next_permute() that modifies a string so that it stores lexicographically next permutation. If current string is lexicographically largest, i.e., “CBA”, then next_permute() returns false.
We first sort the string, so that it is converted to lexicographically smallest permutation. Then we one by one call next_permutation until it returns false.
void permute(string str){ // Sort the string in lexicographically // ascennding order sort(str.begin(), str.end()); // Keep printing next permutation while there // is next permutation do { cout << str << endl; } while (next_permutation(str.begin(), str.end()));}