In one of the previous posts we saw how to compute all permutations of a list recursively. Let us attempt the same, but this time with C++, in what is called divide and conquer approach - essentially divide the input into smaller chunks and recursively call the function on each of the smaller chunk.

Let us compute the permutations of say characters in a string. A string of n characters would have n! permutations. For example, if we have the string “ABC”, the permutations (6 in all) are:

ABC
ACB
BAC
BCA
CBA
CAB

We shall do it by going through the string of characters and iteratively swapping each character with the neighbouring character to get the permutation. For example, for the string “ABC”:


Permutations of "ABC"

Here is a function permute() implementing the traversal: We are given a string s with starting index start and ending index end.

void permute(string s, int start, int end) {
  int i;
  if (start == end)
    cout << s << endl;
  else {
    for (i=start; i<=end; i++) {
      swap(s[start], s[i]);
      permute(s, start+1, end);
      swap(s[start], s[i]);
    }
  }
}

What happens if we use the above algorithms to find permutations of strings that have duplicated characters? For example, the string “AAB” would produce:

AAB
ABA
AAB  (*)
ABA  (*)
BAA
BAA  (*)

As you can see, we are computing the same permutation more than once (marked with *). How can we modify the above function to handle duplicates?