从给定的列表中生成所有可能的k-mer（字符串组合）

Question

我有一个由20个字符组成的字符串S:

S='ARNDCEQGHILKMFPSTWYV'

我需要从给定的输入k生成所有可能的k-mer组合。

当k == 3时，有8000个组合（20*20*20），输出列表如下：

output = ['AAA', 'AAR', ..., 'AVV', ..., 'VVV'] #len(output)=8000

当 k == 2 时，有400种组合（20*20），输出列表如下：

output = ['AA', 'AR', 'AN', ..., 'VV'] #len(output)=400

当k == 1时，仅有20种组合：

output =['A', 'R', 'N', ..., 'Y', 'V'] #len(output)=20

如果数字k是固定的，比如说k == 3，那么我知道如何做到这一点：

for a in S:
   for b in S:
      for c in S:
         output.append(a+b+c)
#then len(output)=8000

但是数字k是随机选择的。 我尝试使用排列，但它不会给我像'AAA'这样有重复字母的字符串，但也许我做错了。

- JY078

Answer 1

你需要的是 itertools.product()。你可以使用 repeat 参数来指定算法中的 k 的数量。

from itertools import product
...
list(product('ARNDCEQGHILKMFPSTWYV', repeat=2)) # len = 400
list(product('ARNDCEQGHILKMFPSTWYV', repeat=3)) # len = 8000

记住它默认返回字符元组，如果你想要字符串，你可以使用列表生成式连接，如下所示：

[''.join(c) for c in product('ARNDCEQGHILKMFPSTWYV', repeat=3)]
# ['AAA', 'AAR', ..., 'AVV', ..., 'VVV']

- umutto

Answer 2

你可以使用 itertools.product 来生成随机值 k:

import itertools
import random
S = 'ARNDCEQGHILKMFPSTWYV'
final_results = map(''.join, itertools.product(*[S]*random.randint(1, 10)))

- Ajax1234

Answer 3

只需在范围 0..L^k-1 中生成随机整数 V，其中 L 是字符串长度，k 是 k-mer 的长度。然后构建相应的组合。

V = Random(L**k)
for i in range(k):
    C[i] = A[V % L]       ///i-th letter using integer modulo
    V = V // L            ///integer division

- MBo