如何限制排列数

Question

我有大约 20 个短字符串需要排列。我只想要 len == 8.

的排列

我想避免计算每个可能的排列，如下所示：

import itertools
p = itertools.permutations([s1, s2, s3, s4, s5, s6,...])
for i in p:
    s = ''.join(j for j in i)
    if len(s)==8:
        print(s)

但这太慢了吧？如何减少计算次数？（不花费处理和 RAM）。

Answer 1

首先，显而易见的事情是过滤掉所有长度大于 8 的字符串：

newList = [i for i in [s1, s2, s3, s4, s5, s6, ...] if len(i) <= 8]

然后，您可以使用itertools.permutations的第二个参数来设置您想要的项目数。如果列表中没有空字符串，则永远不需要超过 8 个项目，因此我们可以使用 8 作为第二个参数：

p = itertools.permutations(newList, 8)

但是，如果您的任何字符串 比一个字符长 ，这将无法满足您的需求，因为它只会 return 排列8 项。解决此问题的一种方法是遍历各种长度：

pList = [itertools.permutations(newList, length) for length in range(1, 9)]

然而，在这里你最终会得到大量的排列来过滤：P(20, 8) + P(20, 7) + ... P(20, 1) = 大致 5.5 billion ，这是不切实际的工作。

一个不同的方向

我们不使用排列，而是使用组合，其中的组合要少得多（“仅”263,949）。回想一下，在组合中，组合项的顺序无关紧要，而在排列中则很重要。因此我们可以使用较小的一组组合来过滤我们想要的长度 8：

cList = (combo for length in range(1, 9) 
    for combo in itertools.combinations(newList, length) 
    if len(''.join(combo)) == 8)

使用 () 而不是 [] 将使它成为一个生成器而不是一个列表，以延迟评估直到我们真正需要它。现在我们很接近了！

我们可以通过对 cList 中的项目进行排列来得到我们的最终结果：

result = [''.join(perm) for combo in cList 
    for perm in itertools.permutations(combo)]

如何限制排列数

How to limit number of permutations

permutation

python-3.x

一个不同的方向