python之列出所有可能包含 n 个字母的单词

我想列出所有可能包含 n 个字母的单词，其中第一个字母可以是 a1 或 a2，第二个可以是 b1、b2 或 b3，第三个可以是 c1 或 c2，...这是一个简单的示例输入- n=2 的输出，每个字母有 2 个备选方案:

• 输入 = [["a","b"],["c","d"]]
• output = ["ac", "ad", "bc", "bd"]

我尝试通过首先使用前 2 个字母创建所有可能的单词来递归地执行此操作，所以像这样:

def go(l): 
    if len(l) > 2: 
        head = go(l[0:2]) 
        tail = l[2:] 
        tail.insert(0, head) 
        go(tail) 
    elif len(l) == 2: 
        res = [] 
        for i in l[0]: 
            for j in l[1]: 
                res.append(i+j) 
        return res 
    elif len(l) == 1: 
        return l 
    else: 
        return None 

但是，对于较大的 n 或每个字母有很多替代方案，这变得非常慢。解决这个问题的更有效方法是什么？

谢谢

请您参考如下方法:

我想你只是想要itertools.product这里:

>>> from itertools import product 
>>> lst = ['ab', 'c', 'de'] 
>>> words = product(*lst) 
>>> list(words) 
[('a', 'c', 'd'), ('a', 'c', 'e'), ('b', 'c', 'd'), ('b', 'c', 'e')]` 

或者，如果您希望将它们连接成单词:

>>> [''.join(word) for word in product(*lst)] 
['acd', 'ace', 'bcd', 'bce'] 

或者，以你的例子:

>>> lst = [["a","b"],["c","d"]] 
>>> [''.join(word) for word in product(*lst)] 
['ac', 'ad', 'bc', 'bd'] 

当然，对于非常大的 n 或非常大的字母集(大小 m)，这会很慢。如果要生成指数级大的输出集 (O(m**n))，这将花费指数时间。但至少它具有常数空间而不是指数空间(它一次生成一个产品，而不是所有产品的巨大列表)，并且会比你在去往的路上快一个不错的常数因子，而且它是更简单，也更难出错。