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

Question

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

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

Answer 1

最简单的方法如下：

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)，维基百科页面上的排列在标题Generation in lexicographic order下给出了简单的描述。如果您感觉雄心勃勃，您可以使用简单的更改在 O(1) 中生成下一个排列