排序与订单

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”顺序的排列大致相同。