Creating combinations with restrictions to each element without retrospective filtering

user_11101348 0
Viewed 73

I need to create all combinations of a list but each element has a lower and upper boundary (increasing with each digit by +2).

For example with n=4: All combinations from [0, 1, 2, 3] (lower boundaries) to [0, 2, 4, 6] (upper boundaries) should result in:

[[0, 1, 2, 3],
 [0, 1, 2, 4],
 [0, 1, 2, 5],
 [0, 1, 2, 6],
 [0, 1, 3, 4],
 [0, 1, 3, 5],
 [0, 1, 3, 6],
 [0, 1, 4, 5],
 [0, 1, 4, 6],
 [0, 2, 3, 4],
 [0, 2, 3, 5],
 [0, 2, 3, 6],
 [0, 2, 4, 5],
 [0, 2, 4, 6]]

The straight forward solution is to use itertools.combinations(range(2*n-1),n) and then filter out all non-valid. But that creates lots of invalid combinations first and then is further slowed down by a filter run through all. That is too inefficient for large n in my case.

I need a solution that does not even attempt to loop higher for each digit than possible and only create combinations within the boundaries for each digit.

I'm sure there is a simple solution with nested loops or backtracking but I can't find it.

combinations itertools combinatorics python
3 Answers

Here's a solution using recursion:

def n_increasing(n, start=0, end=0): 
    if n == 0: 
        yield [] 
        return 
    for choice in range(start, end+1): 
        for remaining in n_increasing(n-1, choice+1, end+2):
            yield [choice, *remaining]

Usage:

>>> list(n_increasing(4))
[[0, 1, 2, 3],
 [0, 1, 2, 4],
 [0, 1, 2, 5],
 [0, 1, 2, 6],
 [0, 1, 3, 4],
 [0, 1, 3, 5],
 [0, 1, 3, 6],
 [0, 1, 4, 5],
 [0, 1, 4, 6],
 [0, 2, 3, 4],
 [0, 2, 3, 5],
 [0, 2, 3, 6],
 [0, 2, 4, 5],
 [0, 2, 4, 6]]
user_10162160

Here's a solution to a more general problem, where you pass the lower and upper bound sequences as parameters:

def constrained_combinations(lower, upper):
    lower, upper = list(lower), list(upper)
    n = len(lower)
    if len(upper) != n:
        raise ValueError('lower and upper bound sequences must have same length')

    # eliminate impossible options
    for i in range(1, n):
        lower[i] = max(lower[i], lower[i-1] + 1)
        upper[-i-1] = min(upper[-i-1], upper[-i] - 1)
    if any(low > high for low, high in zip(lower, upper)):
        return () # no solutions

    def helper(t, i):
        if i == n:
            yield t
        else:
            a, b = lower[i], upper[i]
            if t: a = max(a, t[-1] + 1)
            for j in range(a, b + 1):
                yield from helper(t + (j,), i + 1)

    return helper((), 0)

Example:

>>> gen = constrained_combinations([0, 1, 2, 3], [0, 2, 4, 6])
>>> list(gen)
[(0, 1, 2, 3),
 (0, 1, 2, 4),
 (0, 1, 2, 5),
 (0, 1, 2, 6),
 (0, 1, 3, 4),
 (0, 1, 3, 5),
 (0, 1, 3, 6),
 (0, 1, 4, 5),
 (0, 1, 4, 6),
 (0, 2, 3, 4),
 (0, 2, 3, 5),
 (0, 2, 3, 6),
 (0, 2, 4, 5),
 (0, 2, 4, 6)]
user_122990000

You can use recursion with a generator:

a, b = [0, 1, 2, 3], [0, 2, 4, 6]
def combos(d, c = []):
  if not d:
     yield c
  else:
     yield from [b for i in range(*d[0]) for b in combos(d[1:], c+[i]) if not c or i > c[-1]]

print(list(combos(list(zip(a, [i+1 for i in b])))))

Output:

[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2, 5]
[0, 1, 2, 6]
[0, 1, 3, 4]
[0, 1, 3, 5]
[0, 1, 3, 6]
[0, 1, 4, 5]
[0, 1, 4, 6]
[0, 2, 3, 4]
[0, 2, 3, 5]
[0, 2, 3, 6]
[0, 2, 4, 5]
[0, 2, 4, 6]
user_73267380
Related