可以并行生成排列吗？

Question

我想知道是否可以加快排列的生成。具体来说，我使用 [a-z] 中的 8 个，我想使用 [a-zA-Z] 中的 8 个和 [a-zA-Z0-9] 中的 8 个。我知道这会很快花费大量时间 space.

即使是小写 ASCII 字符的长度为 8 的排列也需要一段时间并生成千兆字节。我的问题是我不了解底层算法，所以我无法开始弄清楚我是否可以将问题拆分成更小的任务，而不是稍后将它们合并在一起。

我用来生成排列列表的 python 脚本：

import string
import itertools
from itertools import permutations

comb = itertools.permutations(string.ascii_lowercase, 8)

f = open('8letters.txt', 'w')
for x in comb:
        y = ''.join(x)
        f.write(y + '\n')

f.close()

有谁知道如何将其划分为子任务并稍后将它们组合在一起？有可能吗？

我可能会尝试一种（可能）更快的方法，但我在使用 C++ 及其 std::next_permutation() 时遇到了问题，所以我无法验证它是否可以加快速度还差一点。

如果我可以将其划分为 16 个任务，并在 16 个 Xeon CPU 上运行，然后加入结果，那就太好了。

Answer 1

如果只是置换和替换，那会很简单：只需并行化字符串的第一个字母，然后让每个线程添加字符串的尾部。这将为您提供 26 个独立任务。如果这还不够，您可以并行化前两个字母。

您想要一个排列而不用替换，所以问题不会平凡分解。如果只想从一组 26、52 和 62 中挑选 8 个字母，则可以做一件天真的粗暴事情：在第一个字母上并行化，让线程只创建带替换的尾部并丢弃包含重复项的生成字符串。但是当你想从26个字母中挑出25个时，这就变得很浪费了。

有了这个想法，我们可以做得更好！我们对字符串的第一个字母进行并行化处理，然后使用集合中的七个元素生成所有排列，不包括我们开始的字母。这样我们可以有 26 个任务（或 52 或 62）并且仍然使用该算法。这可能看起来像这样：

# Use whatever chars you want as the set.
chars = set(string.ascii_lowercase)

# We iterate through all the possible heads. This exact loop will be
# parallelized in the end.
for head in chars:
    # Exclude the head from the set.
    remaining_chars = chars - set(head)

    for tail in itertools.permutations(remaining_chars, 7):
        string = head + ''.join(tail)

        # Store the string in your list/file.

为了利用多个核心，我们使用了一个池。为此，我们首先需要一个函数来映射。这只是上面的一点重构：

def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 7)]

    return strings

现在我们可以在其他地方创建一个池并让它映射到头上：

with multiprocessing.Pool() as pool:
    all_strings = pool.map(make_strings, chars)

池只获得了需要的 __enter__ 和 __exit__ 属性 Python 3，所以我假设我们使用它。

完成后，将列表列表展平为普通字符串列表：

strings = [
    string
    for sub_list in all_strings
    for string in sub_list]

由于 26 是 16 个核心的奇数，我们可以考虑用 itertools.permutation(remaining_chars, 2) 创建头部，然后使用集合减法生成最后 6 个数字。

这是 Python 3 的完整工作脚本，总结了所有内容：

import itertools
import multiprocessing
import string


chars = set(string.ascii_lowercase)


def make_strings(head):
    remaining_chars = chars - set(head)
    strings = [
        head + ''.join(tail)
        for tail in itertools.permutations(remaining_chars, 3)]

    return strings


def main():
    with multiprocessing.Pool() as pool:
        all_strings = pool.map(make_strings, chars)

    strings = [
        string
        for sub_list in all_strings
        for string in sub_list]

    print(strings[:100])


if __name__ == '__main__':
    main()

可以并行生成排列吗？

Can generating permutations be done in parallel?

python

parallel-processing

permutation

combinatorics