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

Using a recursive generator

There isn't anything like a built-in solution for this algorithm, but it's easy to express the desired output recursively. A valid output combination of k-many inputs looks like an arbitrarily selected first element, followed by a combination of k-1-many elements that:

• appear after the first element within the original input sequence (to distinguish combinations from permutations)

• don't share a common ith value, for 0 <= i < n

Thus, we can filter the input sequence according to those criteria, then use recursion to get the possibilities for the remaining elements, and prepend our chosen first element. By iterating over possible first elements within the recursion, we get every desired result.

Accumulating a list of the results would be annoying with recursion, but in Python we can write a recursive generator to avoid the problem. We iterate over possibilities yielded from a recursive call to prepend a first element, and then iterate over possible first elements.

To clarify the logic, we can use a helper function to do the filtering.

The resulting implementation:

def no_common_elements(candidates, word):
    return [
        c for c in candidates
        if all(cl != wl for cl, wl in zip(c, word))
    ]

def distinct_word_combinations(candidates, k):
    if len(candidates) < k:
        return # avoid doing tons of recursion through hopeless cases
    if k == 0: # base case
        yield ()
        return
    for i, first in enumerate(candidates):
        new_candidates = no_common_elements(candidates[i+1:], first)
        for result in distinct_word_combinations(new_candidates, k-1):
            yield (first,) + result

This gives up the performance benefits that itertools.combinations can offer by iterating and/or recursing at the C level, but it prunes branches ahead of time so that everything is generated directly.

In my testing, this is slower for short combinations, but (as expected) much faster for the hard cases:

>>> timeit.timeit("brute_force(two, 3)", globals=globals(), number=1)
0.011705408978741616
>>> timeit.timeit("list(distinct_word_combinations(two, 3))", globals=globals(), number=1)
0.015882118023000658
>>> timeit.timeit("brute_force(two, 8)", globals=globals(), number=1)
51.998020388011355
>>> timeit.timeit("list(distinct_word_combinations(two, 8))", globals=globals(), number=1)
0.048423305968753994

When given a larger input set, however, this approach gets bogged down very easily. With a full set of two-letter words, the brute force approach is about 6 times as fast, and the original version that's specific to n and k values is much faster still. Even with n=4, the recursive generator still loses handily.

This approach also, unfortunately, can't recognize the case where k exceeds the number of possibilities for one of the elements. With the restricted alphabet, this isn't a problem; but while a human can instantly tell that there are no 27-word combinations meeting the condition among the full set of 127 candidate words, this algorithm will still take impossibly long to reach the same conclusion.

posted about 1 month ago

CC BY-SA 4.0

1mo ago

Karl Knechtel‭

2180 reputation 39 54 281 87

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.

posted about 1 month ago

CC BY-SA 4.0

Karl Knechtel‭

2180 reputation 39 54 281 87