Algorithm to list all unique permutations of numbers contain duplicates

Question

The problem is: Given a collection of numbers that might contain duplicates, return all unique permutations.

The naive way is using a set (in C++) to hold the permutations. This takes O(n! × log(n!)) time. Is there better solution?

Answer 1

The simplest approach is as follows:

1. Sort the list: O(n lg n)
2. The sorted list is the first permutation
3. Repeatedly generate the "next" permutation from the previous one: O(n! * <complexity of finding next permutaion>)

Step 3 can be accomplished by defining the next permutation as the one that would appear directly after the current permutation if the list of permutations was sorted, e.g.:

1, 2, 2, 3
1, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...

Finding the next lexicographic permutation is O(n), and simple description is given on the Wikipedia page for permutation under the heading Generation in lexicographic order. If you are feeling ambitious, you can generate the next permutation in O(1) using plain changes