Write a function to print all the possible permutations of a string. Now, modify the algorithm to discard duplicates.

Below is a sample implementation that prints all possible permutations of a string:
#include
#include
const int MAX_STR = 20;
void CopyStr(char *s2, char *s1, int i)
{
for (int j = 0, k = 0, len = strlen(s2); j < len; j++) {
if (i != j) {
s1[k++] = s2[j];
}
}
s1[k] = '\0';
}
void Permute(char *str1, char *str2)
{
int len = strlen(str1);
if (len == 1) {
//If you do not want to print duplicates, put the result in a
// hash and then print the hash table.
cout << str2 << str1 << "\n";
return;
}
for (int i = 0; i < len; i++) {
char currentChar = str1[i];
char str3[MAX_STR];
CopyStr(str1, str3, i);
int len2 = strlen(str2);
str2[len2] = currentChar;
str2[len2+1] = '\0';
Permute(str3, str2);
str2[len2] = '\0';
}
}
int main ()
{
char someStr[MAX_STR], someOtherStr[MAX_STR];
cout << "Enter a string(less then << MAX_STR << “characters:” ";
cin >> someStr;
someOtherStr[0] = '\0';
cout << "\n\nThe permutations of " << someStr <<" are: \n";
Permute(someStr, someOtherStr);
return 1;
}
There are other much more interesting and optimal ways to avoid printing duplicates. For example,
if the For loop kept a “currentChar history” as it went through the loop, it could skip the call to
Permute() if the character was already in its history, since it knows only duplicate permutations
would be generated. This is both faster and much more memory-efficient, since the total number of
permutations you’d have to store in the hash table grows exponentially with the length of the string
– try running this on even “abcdefghij” and you’ll get 10! = 3628800 permutations. At 10 bytes per
word, that is 36 MB of RAM, plus the hash table overhead. A 15-letter word would take over 13
terabytes! As you can see, a hash table answer is obvious, but clearly is not practical.