在某些固定元素的Python中的排列方法

花了相當多的時間試圖想出一種方法（我認爲）應該是一個相對簡單的過程，我已經設法編寫代碼來生成結果（感謝這個精彩論壇的建議！），但根據我的計算，計算所有可能性需要幾年的時間，所以我正在拼命尋找一些幫助，因爲我害怕我的計算機可能無法看到那一天。 :)任何輸入將非常感激！在某些固定元素的Python中的排列方法

我想實現的是從10個唯一條目列表（例如['A'，'B'，'C'，'D'，'E'，'F'，'G'，H '，'I'，'J']），得到字符串長度爲10的所有置換，但要求1個元素（例如'C'）應該出現3次，並且在所有可能的位置。

現在我使用：

options = ['A','B','C','D','E','F','G','H','I','J'] 
def combos(options,n): 
    if (n <= 0): return 
    for s in options: 
     if len(s) <= n: yield s 
     for t in combos(options,n-len(s)): yield s+t 

for x in combos(options,10): 
    if x.count("C") == 3 and len(x) == 10: 
     print x

這種方式，它是計算所有可能的排列，並選取具有3「CS」的那些，並因此產生大量不必要的排列不包含3 'Cs'，因此爲什麼需要更長的時間。有沒有人有任何建議，讓我可以讓Python在產生排列的同時遵守3x'C'限制？

很多，很多預先感謝！

來源

2012-08-28 les_paulde

BrenBarn提出什麼可以給這個：

from itertools import product, combinations 

otheroptions = ['A','B', 'D','E','F','G','H','I','J'] 
c = "C" 
l = 10 
nc = 3 

for t in product(otheroptions, repeat=l-nc): 
    for p in combinations(range(l), nc): 
     r = list(t) 
     for i in p: 
      r[i:i] = [c] 
     print "".join(r)

來源

2012-08-28 09:45:44 MatthieuW

最簡單的方法是使用其他字母生成7個元素的排列，然後交錯三個Cs。

來源

2012-08-28 08:08:04 BrenBarn

itertools是你的朋友：

from itertools import chain, imap, permutations, combinations, repeat 
others = [o for o in options if o != 'C'] 
chain.from_iterable(permutations(*chain(repeat('C', 3), x)) 
        for x in combinations(others, 7))

編輯：這會給排列，不是組合;如果你想要的結果是AAAAAAACCC .. CCCJJJJJJJ那麼它將不得不稍微不同。這裏有一個相當高效的產品/濾波器解決方案：

from itertools import product 
(x for x in product(options, repeat=10) if x.count('C') == 3)

這裏通過BrenBarn的建議是使用交錯的方法：

from itertools import product 
others = [o for o in options if o != 'C'] 
(r[:i] + ('C',) + r[i:j] + ('C',) + r[j:k] + ('C',) + r[k:] 
for r in product(others, repeat=7) 
for i in range(8) for j in range(i, 8) for k in range(j, 8))

你需要測試自己，但對我來說交織方法是顯著更快。

來源

2012-08-28 08:13:18 ecatmur

+1最緊湊的解決方案。 –

非常感謝每個人的偉大建議！交錯方法似乎確實是最快的，現在它可以在一夜之間生成列表，所以我印象深刻！結束MatthieuW的代碼，絕對享受，非常感謝！ –

在某些固定元素的Python中的排列方法

回答

相關問題