排序與訂單

Question

我想寫一個Python函數，執行一個函數類似於itertools.permutation。

import itertools 
for s in itertools.permutations("TCGA****") 
    print s 

從這樣的功能的理想的輸出將是

('*','*','*','*','T', 'C','G','A') 
('*','*','*','T','*', 'C','G','A') 
('*','*','*','T','C', '*','G','A') 
('*','*','*','T','C', 'G','*','A') 
('*','*','*','T','C', 'G','A','*') 
('*','*','T','C','G', 'A','*','*') 
('*','*','T','C','G', '*','*','A') 
('*','*','T','C','*', '*','G','A') 
... 
('T', 'C','G','A','*','*','*','*') 

itertools.permutation之間的唯一區別和該功能是，爲了維持即「T」總是先「C」，其先於「G '在'A'之前。

以下是違反此規則

('*','*','T','*','G','C','A','*','*') 

「C」和「G」的順序已改變的例子。

如何在星號中生成排列順序'TCGA'？

Answer 1

一個想法將產生全方位爲您'*'值可能存在指數與itertools.combinations你的列表索引範圍，進而構建每個可能的排列從這些指標，你'TCGA'值填寫相應的每個組合中沒有找到索引。

由於您可以放心地在每次迭代中使用所有TCGA，因此itertools.cycle是一種不斷爲下一個位置獲取適當值的方法。這裏perms被實現爲一個生成器以允許延遲評估。

from itertools import combinations, cycle 

char_cyc = cycle('TCGA') 
combos = combinations(range(8), 4) 

perms = (['*' if i in combo else next(char_cyc) for i in range(8)] 
     for combo in combos) 

print(list(perms)) 

輸出：

[['*', '*', '*', '*', 'T', 'C', 'G', 'A'], ['*', '*', '*', 'T', '*', 'C', 'G', 'A'], ['*', '*', '*', 'T', 'C', '*', 'G', 'A'], ['*', '*', '*', 'T', 'C', 'G', '*', 'A'], ['*', '*', '*', 'T', 'C', 'G', 'A', '*'], ['*', '*', 'T', '*', '*', 'C', 'G', 'A'], ['*', '*', 'T', '*', 'C', '*', 'G', 'A'], ['*', '*', 'T', '*', 'C', 'G', '*', 'A'], ['*', '*', 'T', '*', 'C', 'G', 'A', '*'], ['*', '*', 'T', 'C', '*', '*', 'G', 'A'], ['*', '*', 'T', 'C', '*', 'G', '*', 'A'], ['*', '*', 'T', 'C', '*', 'G', 'A', '*'], ['*', '*', 'T', 'C', 'G', '*', '*', 'A'], ['*', '*', 'T', 'C', 'G', '*', 'A', '*'], ['*', '*', 'T', 'C', 'G', 'A', '*', '*'], ['*', 'T', '*', '*', '*', 'C', 'G', 'A'], ['*', 'T', '*', '*', 'C', '*', 'G', 'A'], ['*', 'T', '*', '*', 'C', 'G', '*', 'A'], ['*', 'T', '*', '*', 'C', 'G', 'A', '*'], ['*', 'T', '*', 'C', '*', '*', 'G', 'A'], ['*', 'T', '*', 'C', '*', 'G', '*', 'A'], ['*', 'T', '*', 'C', '*', 'G', 'A', '*'], ['*', 'T', '*', 'C', 'G', '*', '*', 'A'], ['*', 'T', '*', 'C', 'G', '*', 'A', '*'], ['*', 'T', '*', 'C', 'G', 'A', '*', '*'], ['*', 'T', 'C', '*', '*', '*', 'G', 'A'], ['*', 'T', 'C', '*', '*', 'G', '*', 'A'], ['*', 'T', 'C', '*', '*', 'G', 'A', '*'], ['*', 'T', 'C', '*', 'G', '*', '*', 'A'], ['*', 'T', 'C', '*', 'G', '*', 'A', '*'], ['*', 'T', 'C', '*', 'G', 'A', '*', '*'], ['*', 'T', 'C', 'G', '*', '*', '*', 'A'], ['*', 'T', 'C', 'G', '*', '*', 'A', '*'], ['*', 'T', 'C', 'G', '*', 'A', '*', '*'], ['*', 'T', 'C', 'G', 'A', '*', '*', '*'], ['T', '*', '*', '*', '*', 'C', 'G', 'A'], ['T', '*', '*', '*', 'C', '*', 'G', 'A'], ['T', '*', '*', '*', 'C', 'G', '*', 'A'], ['T', '*', '*', '*', 'C', 'G', 'A', '*'], ['T', '*', '*', 'C', '*', '*', 'G', 'A'], ['T', '*', '*', 'C', '*', 'G', '*', 'A'], ['T', '*', '*', 'C', '*', 'G', 'A', '*'], ['T', '*', '*', 'C', 'G', '*', '*', 'A'], ['T', '*', '*', 'C', 'G', '*', 'A', '*'], ['T', '*', '*', 'C', 'G', 'A', '*', '*'], ['T', '*', 'C', '*', '*', '*', 'G', 'A'], ['T', '*', 'C', '*', '*', 'G', '*', 'A'], ['T', '*', 'C', '*', '*', 'G', 'A', '*'], ['T', '*', 'C', '*', 'G', '*', '*', 'A'], ['T', '*', 'C', '*', 'G', '*', 'A', '*'], ['T', '*', 'C', '*', 'G', 'A', '*', '*'], ['T', '*', 'C', 'G', '*', '*', '*', 'A'], ['T', '*', 'C', 'G', '*', '*', 'A', '*'], ['T', '*', 'C', 'G', '*', 'A', '*', '*'], ['T', '*', 'C', 'G', 'A', '*', '*', '*'], ['T', 'C', '*', '*', '*', '*', 'G', 'A'], ['T', 'C', '*', '*', '*', 'G', '*', 'A'], ['T', 'C', '*', '*', '*', 'G', 'A', '*'], ['T', 'C', '*', '*', 'G', '*', '*', 'A'], ['T', 'C', '*', '*', 'G', '*', 'A', '*'], ['T', 'C', '*', '*', 'G', 'A', '*', '*'], ['T', 'C', '*', 'G', '*', '*', '*', 'A'], ['T', 'C', '*', 'G', '*', '*', 'A', '*'], ['T', 'C', '*', 'G', '*', 'A', '*', '*'], ['T', 'C', '*', 'G', 'A', '*', '*', '*'], ['T', 'C', 'G', '*', '*', '*', '*', 'A'], ['T', 'C', 'G', '*', '*', '*', 'A', '*'], ['T', 'C', 'G', '*', '*', 'A', '*', '*'], ['T', 'C', 'G', '*', 'A', '*', '*', '*'], ['T', 'C', 'G', 'A', '*', '*', '*', '*']] 

---

良好的指示是輸出是正確的事實是的perms長度是70，其是等於8C4（或「8選擇4「），這實際上是您的問題所關心的問題。

Answer 2

我的解決方案是效率比米奇的低很多，但它是解決問題的另一種方法，所以它也可能讓您感興趣。

這裏是我的方法：生成所有可能的「**** XXXX」排列（準確地說是40320），然後，對於每個結果排列，將每個「X」替換爲通緝中「TGCA」中的對應值訂購。 這裏的缺陷是，不會有40320種不同的模式，但只有70％，這意味着：

• 我們必須執行「for」循環40320次時，70就足夠了
• 我們將不得不存儲生成的排列以忽略重複項

但正如我所說，這是看到問題的另一種方式。

>>> import itertools 
>>> already_seen_permutations = set() 
>>> for s in itertools.permutations("****XXXX"): 
...  if s in already_seen_permutations: 
...   continue # duplicate permutation, just ignore it 
...  already_seen_permutations.add(s) 
...  # time to insert TCGA correctly 
...  s = tuple("".join(s).replace("X", "T", 1).replace("X", "C", 1).replace("X", "G", 1).replace("X", "A", 1)) 
...  print(s) 

在我的電腦上，執行代碼大概需要1秒鐘的時間。 就性能而言，與生成「**** TCGA」的所有排列並忽略不遵循「TCGA」順序的排列大致相同。