给定字母表中的所有可能字符串

Question

我试图从给定的字母表（以列表的形式）生成特定长度的所有可能的字符串。

我尝试使用iterools方法（主要是itertools.product），但即使它适用于较小的长度，正如预期的那样，它非常昂贵，假设n = 100。我想我让它运行了大约1个小时仍然没有完成。

在合理的时间范围内实现这一目标的最快方法是什么？

Answer 1

如果你想从字母集大小n生成大小为m的字符串，你不能使用顺序编程模型比Theta(m**n)运行时（每个n字母表可以是m字母之一）做得更好。

下面的递归程序是一个实现（由于递归深度，原则上需要O(n)空间;从技术上讲，我们需要使用str_so_far的字符串列表，因为虽然字符串在Python中是不可变的，但列表是可变的）：

def gen_strings(alpha_set, n):
    def gen_strings_helper(str_so_far, n_remaining):
        if n_remaining == 0:
            all_strings.append(str_so_far)
            return
        for c in alpha_set:
            gen_strings_helper(str_so_far + c, n_remaining - 1)

    all_strings = []
    gen_strings_helper('', n)
    return all_strings

>>> gen_strings(['a', 'b'], 3)
['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']

为了加快速度，你应该研究并行编程模型。

但是，如果n=100和m=26（小写英文字母集），你的输出将是26**100字符串长！