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

Answer 2

1) Some variation on backtracking/recursive search will usually solve this sort of problem. Given a function to return a list of all permutations on (n-1) objects, generate a list of all permutations on n objects as follows: for each element in the list insert the nth object in all possible positions, checking for duplicates. This isn't especially efficient, but it often generates straightforward code for this sort of problem.

2) See Wikipedia at http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

3) Academics have spent a lot of time on details of this. See section 7.2.1.2 of Knuth Vol 4A - this is a large hardback book with the following brief table of contents on Amazon:

Chapter 7: Combinatorial Searching 1

7.1: Zeros and Ones 47

7.2: Generating All Possibilities 281