列出数字的所有唯一排列的算法包含重复项 [英] Algorithm to list all unique permutations of numbers contain duplicates

问题描述

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

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

天真的方法是使用一组(在C ++中)保存排列.这需要 O ( n ！×log( n ！))时间.有更好的解决方案吗?

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

推荐答案

最简单的方法如下:

1. 对列表进行排序:O(n lg n)
2. 排序后的列表是第一个排列
3. 反复从上一个生成下一个"排列:O(n! * <complexity of finding next permutaion>)

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>)

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

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
...

查找下一个词典编排是O(n)，在维基百科页面上对编排的简单描述在标题按字典顺序生成. 如果您有雄心壮志，可以使用普通更改

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

这篇关于列出数字的所有唯一排列的算法包含重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！