Post History

Generating combinations of elements, which are themselves sequences of the same length, where the elements have no value in common at any position

<section class="notice">

This question is adapted from [a question I just helped fix up on Stack Overflow](https://stackoverflow.com/questions/79182496). I'm giving a different motivating example which I think will make it clearer what the requirements are and why a naive approach would take prohibitively long. (Also, I want to attempt an answer, but by personal policy I don't write new answers on Stack Overflow any more.)
</section>

I have a list of two-letter English words [from the Official Scrabble Players' Dictionary](https://scrabble.collinsdictionary.com/word-lists/two-letter-words-in-scrabble/):

```
two = [
    'AA', 'AB', 'AD', 'AE', 'AG', 'AH', 'AI', 'AL', 'AM', 'AN', 'AR', 'AS',
    'AT', 'AW', 'AX', 'AY', 'BA', 'BE', 'BI', 'BO', 'BY', 'CH', 'DA', 'DE',
    'DI', 'DO', 'EA', 'ED', 'EE', 'EF', 'EH', 'EL', 'EM', 'EN', 'ER', 'ES',
    'ET', 'EW', 'EX', 'FA', 'FE', 'FY', 'GI', 'GO', 'GU', 'HA', 'HE', 'HI',
    'HM', 'HO', 'ID', 'IF', 'IN', 'IO', 'IS', 'IT', 'JA', 'JO', 'KA', 'KI',
    'KO', 'KY', 'LA', 'LI', 'LO', 'MA', 'ME', 'MI', 'MM', 'MO', 'MU', 'MY',
    'NA', 'NE', 'NO', 'NU', 'NY', 'OB', 'OD', 'OE', 'OF', 'OH', 'OI', 'OK',
    'OM', 'ON', 'OO', 'OP', 'OR', 'OS', 'OU', 'OW', 'OX', 'OY', 'PA', 'PE',
    'PI', 'PO', 'QI', 'RE', 'SH', 'SI', 'SO', 'ST', 'TA', 'TE', 'TI', 'TO',
    'UG', 'UH', 'UM', 'UN', 'UP', 'UR', 'US', 'UT', 'WE', 'WO', 'XI', 'XU',
    'YA', 'YE', 'YO', 'YU', 'ZA', 'ZE', 'ZO'
]
```
(There are 127 words, out of 676 possible pairs of letters. I'm showing Python code here, but I'm also interested in language-agnostic discussion of the algorithm.)

I want to find *combinations of k words* (say k=3 for example), restricted such that, *within each combination*, all words have a distinct first letter *and* a distinct second letter.

The alphabetically first such combination is `['AA', 'BE', 'CH']`. Note that the combination `['AA', 'BA', 'CH']` isn't valid because the first two words have the same *second* letter `'A'`.

My naive approach is to make all combinations of the words using the standard library `itertools.combinations` (which already rejects invalid "combinations" using the *same word* more than once, and takes order into account), then filter out combinations with a common first word:

```
from itertools import combinations

word_triples = [
    (a, b, c) for a, b, c in combinations(two, 3)
    if a[0] != b[0] and a[0] != c[0] and b[0] != c[0]
    and a[1] != b[1] and a[1] != c[1] and b[1] != c[1]
]
```
This gives a correct result in about a tenth of a second on my machine.

However, there are some problems:

1. The filtering logic would be hard to generalize.

1. **This clearly won't scale**. For groups of 3 words it's simple enough: `itertools.combinations` generates `333375` possibilities, and most of them are actually valid - `len(word_triples)` reports `217503`. But with more words in a combination, the unfiltered input will scale exponentially, while the desired result will grow much more slowly, and even shrink. (In the extreme: there are about 3 * 10<sup>27</sup> possible combinations of 27 words from this list, but clearly *none* of them satisfy the condition as there are only 26 possible letters for each position.)

I did test this for groups of 4 words, writing out all the conditions manually - and as expected, it's dozens of times slower. It has to do twice as many filtering comparisons, while generating 31 times as many candidates. (A more generalized approach using set comprehensions to check for distinct letters is actually even slower, though that presumably reverses at some point.)

**How can I do this more efficiently and directly**? I'm looking for a *fully general* approach - it should be able to handle:

* Inputs where the elements to combine are longer (as long as they're all the same length)

* Inputs which are arbitrary sequences, rather than just strings of English letters

* An arbitrary value for `k`