I have a list of 5 letters ['A', 'B', 'N', 'M','E'].

I want to print all the words (word means a sequence of letters, it doesn't have to be a valid English word) of length 10 letters that have exactly two letters A. Order is important.

I have tried with itertools.product as it appeared to be the most promising solution:

from itertools import product

letters = ['A', 'B', 'N', 'M','E']

for word in product(letters, repeat=10):
    res = ''.join(str(x) for x in word)
    print(res)

The problem with this approach is that I can't really control the number of occurrences of the letter A as it returns the word composed of 10 letters of A.

Is there a solution for this? Thanks

EDIT 1 Example of possible words: BANAMEMNEB : it has only twice the letter A, we don't care about other letters.

CodePudding user response：

The way to do it efficiently is to iterate over all combinations of the positions of the letters 'A', and for each such combination - iterate over all the ways other letters can be positioned, and just insert the 'A's there.

Be warned that with your inputs this will produce almost 3 million words!

On my machine it was printing the words for so long that I had to manually stop execution.

So here is the smaller example:

letters = ['A', 'b', 'c']
num_As = 2
num_total = 4

from itertools import combinations, product
for indices_A in combinations(range(num_total), num_As):
    for rest in product(letters[1:], repeat=num_total - num_As):
        rest = list(rest)
        for index_A in indices_A:
            rest.insert(index_A, 'A')
        print(''.join(rest))

AAbb
AAbc
AAcb
AAcc
AbAb
AbAc
AcAb
AcAc
AbbA
AbcA
AcbA
AccA
bAAb
bAAc
cAAb
cAAc
bAbA
bAcA
cAbA
cAcA
bbAA
bcAA
cbAA
ccAA

CodePudding user response：

This is basically @Vladimir-Fokow's answer translated to your use case:

#!/usr/bin/env python
from itertools import combinations, product
letters =  ['A', 'B', 'N', 'M','E']
first, rest = letters[0], letters[1:]
total_length = 10
first_count = 2
for others in product(rest, repeat=total_length - first_count):
  for indices in combinations(range(total_length),first_count):
    result = list(others)
    for i in indices:
      result.insert(i,first)
    print(''.join(result))

On my iMac this only took about 3 seconds to print out all 2,949,120 words.

CodePudding user response：

A solution would be to filter out the words that do not contain exactly two 'A', as in the following simple code:

from itertools import product
from collections import Counter

letters = ['A', 'B', 'N', 'M','E']

for word in product(letters, repeat=10):
    res = ''.join(word)  # equivalent to res = ''.join(str(x) for x in word) !
    ctr = Counter(res)
    if ctr['A'] == 2:
        print(res)

This can also be written with one-line style coding, as follows:

res = [''.join(w) for w in product(letters, repeat=10) if Counter(w)['A'] == 2]

CodePudding user response：

First determine the two indices where the letter "A" will occur, then produce the letters at the other 8 indices:

from itertools import combinations, product

def solve():
    for i, j in combinations(range(10), 2):
        for b in map(list, product("BNME", repeat=8)):
            b.insert(i, "A")
            b.insert(j, "A")
            yield "".join(b)

To print:

for s in solve():
    print(s)

...but don't wait for it. There are 9*10/2 * 4⁸ possible combinations, which is almost 3 million.