列出包含重复的数字的所有唯一排列的算法

问题是：给定一个可能包含重复项的数字集合，返回所有唯一的排列。

最简单的方法是使用集合（在 C++ 中）来保存排列。这需要O(n! × log(n！）） 时间。有更好的解决方案吗？

最简单的方法如下：

1. 对列表进行排序：O(n lg n)
2. 排序后的列表是第一个排列
3. 从前一个排列中重复生成“下一个”排列：O(n! * <complexity of finding next permutaion>)

步骤 3 可以通过将下一个排列定义为如果排列列表已排序则将直接出现在当前排列之后的排列来完成，例如：

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

查找下一个字典排列的时间复杂度为 O(n)，维基百科页面上的标题下给出了简单的排列描述按字典顺序生成 http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order。 如果您雄心勃勃，您可以使用 O(1) 生成下一个排列简单的改变 http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm