列出数字的所有唯一排列的算法包含重复项
问题是:给定一个可能包含重复项的数字集合,请返回所有唯一排列。
天真的方法是使用一组(在C ++中)保存排列。这需要O(n!×log(n!))时间。有更好的解决方案吗?
回答:
最简单的方法如下:
- 排序列表: O(n lg n)
- 排序列表是第一个排列
- 重复从上一个生成“下一个”排列:
O(n! * <complexity of finding next permutaion>)
步骤3可以通过将下一个排列定义为如果排列列表已排序在当前排列之后直接出现的排列来完成,例如:
1, 2, 2, 31, 2, 3, 2
1, 3, 2, 2
2, 1, 2, 3
2, 1, 3, 2
2, 2, 1, 3
...
查找下一个词典编排是O(n),并且在维基百科页面上以词典编排顺序在Generation标题下给出了简单的排列描述。如果您有雄心壮志,则可以使用简单的更改在O(1)中生成下一个排列
以上是 列出数字的所有唯一排列的算法包含重复项 的全部内容, 来源链接: utcz.com/qa/420131.html