查找方式的順序可以重新排列數量

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。不過，我不確定如何建模。建議？