顺序排列

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

我的解决方案比 Mitch 的效率低得多，但这是解决问题的另一种方法，因此您可能也会感兴趣。

这是我的方法：生成“****XXXX”（正好是 40320）的所有可能排列，然后，对于每个结果排列，将每个 "X" 替换为 [=28] 中的相应值=] 在想要的顺序。这里的缺陷是不会有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)

在我的电脑上，执行代码 100 次大约需要一秒钟。在性能方面，它与生成“****TCGA”的所有排列并忽略不遵循 "TCGA" 顺序的排列大致相同。

顺序排列

Permutations with Order

python

permutation