时间戳

首页 > 解决方案 > 用 n 个字母列出所有可能的单词

python - 用 n 个字母列出所有可能的单词

问题描述

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

我尝试通过首先使用前 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 或每个字母的许多替代方案，这变得非常慢。解决这个问题的更有效方法是什么？

谢谢

标签： python

解决方案

我想你只想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)），那将需要指数级的时间。但至少它具有恒定而不是指数空间（它一次生成一个产品，而不是所有这些产品的巨大列表），并且会比你在路上的速度快一个像样的常数因子，而且它是更简单，更难出错。

推荐阅读