问题是：给定数的集合，它可能包含重复，返回所有独特排列。
用简单的方式是使用一组（在C ++）来保持排列。 这需要为O（n！×的log（n！））时间。 有没有更好的解决办法？
Answer 1:
最简单的方法如下：
- 排序列表：
O(n lg n) - 排序列表中是第一置换
- 反复生成与前一个“下一个”置换：
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），并简单说明Wikipedia页面上给出的标题下排列在字典顺序生成 。 如果你感觉雄心勃勃，您可以生成在O下一置换（1）使用普通的变化
Answer 2:
1）回溯/递归搜索一些变化通常会解决这类问题。 给定一个函数来返回上（N-1）的物体的所有排列的列表，生成的所有排列的上n个对象的列表如下：对于列表中的每个元件插入第n个对象中的所有可能的位置，检查重复。 这不是特别有效，但它往往产生简单的代码，这类问题。
2）请参见维基百科在http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
3）学者们花费了大量的时间对这个细节。 见7.2.1.2克努特卷4A - 这是一个大的精装书的亚马逊内容下面介绍一下表：
第7章：组合搜索1
7.1：零和一47
7.2：生成所有可能性281
Answer 3:
你应该阅读我的博客文章对这种置换的（除其他事项外），以获得更多的背景-并按照某些环节存在的。
下面是确实的要求豪斯 - 约翰逊特罗特置换发电机的发电序列后塑造一个版本我辞书排列生成的：
def l_perm3(items):
'''Generator yielding Lexicographic permutations of a list of items'''
if not items:
yield []
else:
dir = 1
new_items = []
this = [items.pop()]
for item in l_perm3(items):
lenitem = len(item)
try:
# Never insert 'this' above any other 'this' in the item
maxinsert = item.index(this[0])
except ValueError:
maxinsert = lenitem
if dir == 1:
# step down
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem, -1, -1)
if i <= maxinsert]:
yield new_item
else:
# step up
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem + 1)
if i <= maxinsert]:
yield new_item
dir *= -1
from math import factorial
def l_perm_length(items):
'''\
Returns the len of sequence of lexicographic perms of items.
Each item of items must itself be hashable'''
counts = [items.count(item) for item in set(items)]
ans = factorial(len(items))
for c in counts:
ans /= factorial(c)
return ans
if __name__ == '__main__':
n = [0, 1, 2, 2, 2]
print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
for i, x in enumerate(l_perm3(n[:])):
print('%3i %r' % (i, x))
assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'
从上面的程序的输出是例如以下：
Lexicograpic Permutations of 5 items: [0, 1, 2, 2, 2]
0 [0, 1, 2, 2, 2]
1 [0, 2, 1, 2, 2]
2 [2, 0, 1, 2, 2]
3 [2, 0, 2, 1, 2]
4 [0, 2, 2, 1, 2]
5 [2, 2, 0, 1, 2]
6 [2, 2, 0, 2, 1]
7 [0, 2, 2, 2, 1]
8 [2, 0, 2, 2, 1]
9 [2, 2, 2, 0, 1]
10 [2, 2, 2, 1, 0]
11 [2, 1, 2, 2, 0]
12 [1, 2, 2, 2, 0]
13 [2, 2, 1, 2, 0]
14 [2, 2, 1, 0, 2]
15 [1, 2, 2, 0, 2]
16 [2, 1, 2, 0, 2]
17 [2, 1, 0, 2, 2]
18 [1, 2, 0, 2, 2]
19 [1, 0, 2, 2, 2]
Answer 4:
这一次我想我是怎样写出来的手工排列，并把该方法的代码更短，更好以后发明：
def incv(prefix,v):
list = []
done = {}
if v:
for x in xrange(len(v)):
if v[x] not in done:
done[v[x]] = 1
list = list + incv(prefix+v[x:x+1],v[:x] + v[x+1:])
else:
list.append(''.join(prefix))
return list
def test(test_string,lex_ord=False):
if lex_ord:
test_string = [x for x in test_string]
test_string.sort()
p = incv([],[x for x in test_string])
if lex_ord:
try_p = p[::]
try_p.sort()
print "Sort methods equal ?", try_p == p
print 'All', ','.join(p), "\n", test_string, "gave", len(p), "permutations"
if __name__ == '__main__':
import sys
test(sys.argv[1],bool(sys.argv[2] if len(sys.argv) > 2 else False))
笔记
-
incv递增排列矢量找到他们。 它还能够正确处理重复字母。 -
test打印出所有的排列和他们的测试串计数。 这也可以确保如果您请求字典顺序的排序之前和方法后的排序是相同的。 由于原字符串命令和增量置换函数把字符串转换由给定字母的下一个字典字符串这应该是真实的。
该脚本可以通过在命令提示符下运行：
python script.py [test_string] [optional anything to use lexicographic ordering]
Answer 5:
我略有改善Paddy3118的解决方案 ，所以它现在非递归，懒惰评估（完全基于发电机）和30％的速度约。
def _handle_item(xs, d, t):
l = len(xs)
try:
m = xs.index(t)
except ValueError:
m = l
if d:
g = range(l, -1, -1)
else:
g = range(l + 1)
q = [t]
for i in g:
if i <= m:
yield xs[:i] + q + xs[i:]
def _chain(xs, t):
d = True
for x in xs:
yield from _handle_item(x, d, t)
d = not d
def permutate(items):
xs = [[]]
for t in items:
xs = _chain(xs, t)
yield from xs
PS我已经注意到Paddy3118做了他实现用发电机组为好，而我一直反对的博客文章，这是更多的内存intensitive实施。 我反正张贴这，因为这个版本可能被认为是更清洁。
Answer 6:
递归版本。 此计算针对n /（米* K！）（米组字符数，在每一组重复字符的k个！：
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_CHARS_STRING=100;
int CURRENT_CHARS=0;
char STR[MAX_CHARS_STRING];
void myswap(int i, int j){
char c=STR[i];STR[i]=STR[j];STR[j]=c;
}
bool IstobeExecuted(int start,int position){
if(start==position)
return true;
for(int i=position-1;i>=start;i--){
if(STR[i]==STR[position])
return false;
}
return true;
}
void Permute(int start, int end,int& perm_no){
if(end-start<=1){
if(STR[end]==STR[start]){
cout<<perm_no++<<") "<<STR<<endl;
return;
}
cout<<perm_no++<<") "<<STR<<endl;
myswap(start, end);
cout<<perm_no++<<") "<<STR<<endl;
myswap(start,end);
return;
}
for(int i=start; i<=end;i++){
if(!IstobeExecuted(start,i)){
continue;
}
myswap(start,i);
Permute(start+1,end,perm_no);
myswap(start,i);
}
}
int main(){
cin>>STR;int num=1;
Permute(0,strlen(STR)-1,num);
return 0;
}
希望这可以帮助
文章来源: Algorithm to list all unique permutations of numbers contain duplicates
