Post History

## Using filtered products of candidates, over combinations of first letters

Let's consider the *n*=2 case first. (For higher *n*, we can use the same sort of recursive generator approach as in my other answer, but recursing on *n* instead of *k*.)

Partition the input words according to the first letter; we can take at most one word from each. If we generate combinations of *k* of these groups, then for each such combination, we have a list of possibilities for the first, second etc. word in a valid output.

So, we can generate the Cartesian product of such a combination in order to get a bunch of candidates (where the first letter is guaranteed distinct), and then filter them to ensure the second letter is distinct as well.

Thus:

```
from itertools import combinations, product

def distinct_word_combinations(words, k):
    by_first_letter = {}
    for word in words:
        by_first_letter.setdefault(word[0], []).append(word)
    for first_letters in combinations(by_first_letter.keys(), k):
        word_lists = [by_first_letter[l] for l in first_letters]
        for candidate in product(*word_lists):
            if len({word[1] for word in candidate}) == len(candidate):
                yield candidate
```

Also notice the improved test for distinct letters in a given position: instead of doing O(N^2) comparisons, we build a `set` and check its length, which is O(N).

This doesn't do as good of a job of avoiding generating useless candidates; but in many ways it's the best of both worlds. Even for small *k* it's much faster:

```
>>> timeit.timeit("list(distinct_word_combinations(two, 3))", globals=globals(), number=1)
0.0022177270147949457
```

and it still does enough pruning to beat the recursive generator approach on this input for 8-word groups:

```
>>> timeit.timeit("list(distinct_word_combinations(two, 8))", globals=globals(), number=1)
0.030769726959988475
```

We can easily calculate how many combinations it considers for filtering:

```
from itertools import combinations
from math import prod

def candidate_count(words, k):
    result = 0
    by_first_letter = {}
    for word in words:
        by_first_letter[word[0]] = by_first_letter.get(word[0], 0) + 1
    for first_letters in combinations(by_first_letter.keys(), k):
        result += prod([by_first_letter[l] for l in first_letters])
    return result
```

We find that, for example, 23437 candidates are generated for *k*=4 (of which 9698 are valid), compared to 58905 for the brute force approach.

We can also comfortably handle egregious cases where the number of words requested is impossibly high (not enough symbols are used in the first position) - since `combinations(by_first_letter.keys(), k)` will promptly generate an empty sequence when `k > len(by_first_letter.keys())`.

Of course, the choice of the "key" position to use is arbitrary - for the *n*=2 case we could equally well group the input according to the *second* letter, generate candidates, and then make sure the *first* letter is distinct.