查找方式的顺序可以重新排列数量

Question

我如何才能找到路数的数字序列（可能含有类似物品）可以重新排列，使一些不放在同一个地方，因为它或它的类似号码被放置。

例如，[0,0,0,1,1,1]也只能用一种方法重新排列，这是[1,1,1,0,0,0]。

[0,0,0,1,1,1,1]不能以任何方式布置。

[1,2,2,14]可以设置在2种方式即[2,1,14,2], [2,14,1,2]。

[1,1,2,2,14]可以布置在4种方式即[14,2,1,1,2], [2,2,14,1,1], [2,2,1,14,1], [2,14,1,1,2]。

数学解决方案是可用的，但我正在考虑使用编程概念的一些简单的方法。数学代码是有点像这个..（对不起，我不能以正确的格式上传）

∫∞0 Ln1(x)..Lnr(x)e−xdx 

其中R是项目的数量，NI是项目出现的次数我和LK是第k个拉盖尔多项式。例如，对于1,1,2,2,14，我们有R = 3，N1 = 2，N2 = 2，N3 = 1，所以到一个标志重排的数量是

∫∞0 L2(x)L2(x)L1(x)e−xdx 
= ∫∞0 12(x2−4x+2)12(x2−4x+2)(1−x)e−xdx 
= ∫∞0(−14x5+94x4−7x3+9x2−5x+1)e−xdx 
= −4 

但我在想，是否有任何python库可以根据我们的需要生成所有的排列组合。

Answer 1

蛮力：

import itertools 
def arrangements(arr): 
    p = itertools.permutations(arr) 
    return set(item for item in p if all(x!=y for x,y in zip(item,arr))) 

结果：

>>> arrangements([0,0,0,1,1,1]) 
{(1, 1, 1, 0, 0, 0)} 
>>> arrangements([0,0,0,1,1,1,1]) 
set() 
>>> arrangements([1,2,2,14]) 
{(2, 14, 1, 2), (2, 1, 14, 2)} 
>>> arrangements([1,1,2,2,14]) 
{(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)} 

Answer 2

您是否尝试过itertools.permutations？

http://docs.python.org/library/itertools.html#itertools.permutations

import itertools 

def my_combos(val): 
    results = [] 
    l = itertools.permutations(val, len(val)) 
    for c in l: 
     if all([x != y for (x,y) in zip(c,val)]): 
      results.append(c) 
    return list(set(results)) 


print my_combos([0,0,0,1,1,1]) 
print my_combos([1,1,2,2,14]) 

收率：使用itertools

[(1, 1, 1, 0, 0, 0)] 
[(2, 14, 1, 1, 2), (2, 2, 1, 14, 1), (14, 2, 1, 1, 2), (2, 2, 14, 1, 1)] 

Answer 3

更复杂，但应该还是比较快一点长的输入序列：

from collections import Counter 

def _rearrange(orig, rem): 
    if len(orig)==1: 
     v = rem[0][0] 
     if v != orig[0]: 
      yield [v] 
    else: 
     o, orig = orig[0], orig[1:] 
     for i,(v,c) in enumerate(rem): 
      if v != o: 
       for r in _rearrange(orig, rem[:i]+([(v,c-1)] if c>1 else [])+rem[i+1:]): 
        yield [v]+r 

def rearrange(orig): 
    if len(orig) > 1: 
     return list(_rearrange(orig, Counter(orig).items())) 
    else: 
     return [] 

def main(): 
    print rearrange([0,0,0,1,1,1]) 
    print rearrange([1,1,2,2,14]) 

if __name__=="__main__": 
    main() 

结果

[[1, 1, 1, 0, 0, 0]] 
[[2, 2, 1, 14, 1], [2, 2, 14, 1, 1], [2, 14, 1, 1, 2], [14, 2, 1, 1, 2]] 

。

编辑：功能运行时相比，我得到：

（蓝添的，绿色矿山;点是数据线对数的最佳拟合（最小二乘数据）; x轴是序列长度，y轴是以秒为单位的运行时间（对数刻度）。对于每个序列长度，数据点最好在20个随机序列中的每一个上运行10次。）

结论：

• 蒂姆的FN的运行时长为7.44 * N;我的成长为3.69 * * n。

• 了十来项序列，他FN平均53.9s VS 0.93s矿;对于序列中的每个额外项目，差异略微超过双倍。

• 他FN有一个更加一致的运行;我的变化很大，取决于序列中重复项目的数量。

• 拟合直线，看起来并不像最好的预测;运行时间应该是n！的函数，而不是k * * n。不过，我不确定如何建模。建议？