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

Question

The NY Times has a game called Spelling Bee, with the goal of listing valid English words. The initial conditions are a set of seven letters, with one letter designated as 'required to be in each word, at least once'. The minimum word length is 4, and there is no maximum. To amuse myself I started to write a program to generate such words.

An example: on October 12,2021, the set of letters is 'cpithde', and 'c' is the required letter. Acceptable words include:

  pitch
  pitched  # this uses all seven letters
  hide
  chide
  diced

and so on.

I know about itertools, with its permutations('abcd', N), combinations() with and without replacement, and product().

None of those do exactly what I want. I know I can brute-force the generation of the appropriate strings, but I am curious if there is a combination of library functions that will do it.

To clarify the problem: consider the word diced. The letter d appears two times. And on October 11, the word riffraff was a valid and high-scoring word, with twice-duplicated r and 4-times-duplicated f. The itertools functions seem to generate (n choose k), where are results are always of length k. I want to generate, for example, (n choose [k for k in range(4, 12)])

Or this:

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

And then I will test each candidate word in result against an English dictionary.

Any guidance is appreciated.

Answer 1

You're looking for the 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)  

Note that this doesn't include the required letter, since you specified that "hide" is a valid output and haven't mentioned how it would be implemented (e.g. first letter in letters or separately).

Demo

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

Output:

True
True
True
True
True

---

For checking against an English dictionary, you could do something like this:

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

Or, this is slower:

words = lexicon & possible_words