是否有一个 Python 库函数，给定一个字符串，将生成任何长度的所有排列，并重复？

Question

纽约时报有一个名为拼字比赛的游戏，目标是列出有效的英语单词。初始条件是一组七个字母，其中一个字母指定为 'required to be in each word, at least once'。最小字长为 4，没有最大值。为了自娱自乐，我开始编写一个程序来生成这样的单词。

举例：2021年10月12日，字母集合为'cpithde'，'c'为所需字母。可接受的字词包括：

  pitch
  pitched  # this uses all seven letters
  hide
  chide
  diced

等等。

我了解 itertools，及其排列 ('abcd', N)、带替换和不带替换的组合 () 以及 product()。

其中

None 完全符合我的要求。我知道我可以暴力生成适当的字符串，但我很好奇是否有库函数的组合可以做到这一点。

澄清问题：考虑diced这个词。字母 d 出现了两次。而在 10 月 11 日，单词 riffraff 是一个有效且得分高的单词，有两次重复 r 和四次重复 f。 itertools 函数似乎生成（n 选择 k），其中结果总是长度 k。例如，我想生成 (n choose [k for k in range(4, 12)])

或者这个：

    result = spelling_bee_generator('cpithde', 
                                    min=4, 
                                    max=<a reasonably small value here>)

然后我会根据英语词典测试 result 中的每个候选词。

感谢任何指导。

Answer 1

您正在寻找 product(repeat=N)。

from itertools import product

def spelling_bee_generator(letters, min_length, max_length):
    for n in range(min_length, max_length+1):
        for p in product(letters, repeat=n):
            yield ''.join(p)

请注意，这不包括所需的字母，因为您指定“隐藏”是一个有效的输出并且没有提到它是如何实现的（例如 letters 中的第一个字母或单独的） .

演示

possible_words = set(spelling_bee_generator('cpithde', 4, 7))
for word in 'pitch', 'pitched', 'hide', 'chide', 'diced':
    print(word in possible_words)

输出：

True
True
True
True
True

要对照英语词典，您可以这样做：

lexicon: set
words = {
    w for w in spelling_bee_generator('cpithde', 4, 7)
    if w in lexicon
    }

或者，这更慢：

words = lexicon & possible_words

是否有一个 Python 库函数，给定一个字符串，将生成任何长度的所有排列，并重复？

Is there a Python library function that, given a string, will generate all permutations of any length, with repetion?

python

itertools

演示