Создание комбинаций с ограничениями для каждого элемента без ретроспективной фильтрации - PullRequest
Новая
       105

Создание комбинаций с ограничениями для каждого элемента без ретроспективной фильтрации

3 голосов
/ 22 февраля 2020

Мне нужно создать все комбинации списка, но каждый элемент имеет нижнюю и верхнюю границу (увеличивается с каждым di git на +2).

Например, при n = 4: все комбинации от [0, 1, 2, 3] (нижние границы) до [0, 2, 4, 6] (верхние границы) должны приводить к: 

[[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]]

Прямое решение заключается в использовании itertools.combinations(range(2*n-1),n), а затем отфильтровывает все недействительные. Но это сначала создает множество недопустимых комбинаций, а затем еще больше замедляется фильтром, проходящим через все. В моем случае это слишком неэффективно для больших n.

Мне нужно решение, которое даже не пытается на l oop выше для каждого di git, чем возможно, и создает только комбинации в границах для каждого di git.

Я уверен, что есть простое решение с вложенными циклами или возвратом, но я не могу его найти.

Ответы [ 3 ]

2 голосов
/ 22 февраля 2020

Вот решение с использованием рекурсии: 

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]

Использование: 

>>> 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]]
1 голос
/ 22 февраля 2020

Вот решение более общей проблемы, когда вы передаете нижнюю и верхнюю границы последовательности в качестве параметров: 

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)

Пример: 

>>> 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)]
0 голосов
/ 22 февраля 2020

Вы можете использовать рекурсию с генератором: 

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])))))

Выход: 

[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]
...