-1

While there are a lot of solutions for how to find all the (unique) permutations of a string of unique characters, I haven't found solutions that work when the characters are non-unique. I have listed out my idea below and would appreciate feedback, but also feel free to provide your own ideas.

My idea:

To illustrate my algorithm, I'm using the example of the string ABBC, which I want to find all permutations of. Since there are two B's I will be labelling them B1 and B2.

  1. Create a new string by removing all duplicate characters from the original string (e.g. turn AB1B2C into AB1C).
  2. Find all possible permutations of the new string (e.g. AB1C, ACB1, B1AC, etc.). There are many algorithms to do this, since the string's characters are all unique.
  3. Choose one duplicate character. For each permutation, insert the chosen duplicate characters at every "position" of the permutation, except when the character just before the duplicate character has the same value as the duplicate character (e.g. For the permutation AB1C, since the duplicate character is B2, insert it to get B2AB1C, AB2B1C, AB1CB2. Exception: Don't do AB1B2C, since that's just a duplicate of AB2B1C).
  4. Continue to do step 3 but now choose a different duplicate character. (Do this until all duplicate characters have been chosen exactly once.)

Prior research: The answer by Prakhar on this SO question claims to work for duplicates: Generate list of all possible permutations of a string. It might, but I suspect there's a bug in the code.

Community
  • 1
  • 1
randomUser47534
  • 329
  • 1
  • 5
  • 18
  • Next permutation algorithm ([wiki](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)) can handle non-unique characters. – user4003407 May 22 '15 at 02:44
  • possible duplicate of [How to generate all the permutations of a multiset?](http://stackoverflow.com/questions/19676109/how-to-generate-all-the-permutations-of-a-multiset) – Paul Hankin May 22 '15 at 08:36

1 Answers1

0

How about this: suppose that the string with duplicates is of length N. Now consider the sequence 0,1,...N-1. Find all its permutations using one of the known algorithms. For each permutation in this list, generate a corresponding string by using the number in the permutation as an index into the original string. For example, if the string is ABBC, then the sequences will be 0,1,2,3; 0,1,3,2; etc. The sequence 3,0,1,2, as an example, is one of the permutations, and it yields the string CABB