Найти последовательности в списке диапазонов

Question

У меня есть случайный список длин, который содержит информацию о диапазонах:

list = [
 [[7, 12], [6, 12], [38, 44], [25, 30], [25, 29]], 
 [[0, 5], [1, 5], [2, 5], [12, 16], [13, 16], [20, 23], [29, 33], [30, 33]], 
 [[5, 7], [6, 8], [7, 9], [8, 10], [9, 11], [10, 12], [16, 18], [17, 19], [18, 20], [23, 25], [24, 26], [25, 27], [26, 28], [27, 29], [33, 35], [34, 36], [35, 37], [36, 38], [37, 39], [38, 40], [39, 41], [40, 42], [41, 43], [42, 44]]
]

Например, первый элемент [[7, 12], [6, 12], [38, 44], [25, 30]] содержит 4 диапазона 7-12, 6-12, 38-44 и 25-30 et c.

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

Итак, для этого примера: цепочки будут [[6, 12], [12, 16], [16, 18]], [[7, 12], [12, 16], [16, 18]], [[25, 30], [30, 33], [33, 35]] и [[25, 29], [29, 33], [33, 35]]

Сейчас я застрял на работе с длиной более трех список, не может придумать рекурсивное решение.

Answer 1

Вы можете сделать это, не глядя на все перестановки. Начните с последнего элемента и создайте словарь, где ключи являются первым значением в словаре. Затем работайте в обратном направлении по списку и ищите предыдущий ключ, основываясь на втором значении кортежа, добавляемом в массив, когда вы go:

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

Здесь я добавил еще одну пару [12,9] в средний список, чтобы видеть, как она работает с путями ветвления:

from collections import defaultdict
from itertools import chain

l = [
 [[7, 12], [6, 12], [38, 44], [25, 30]], 
 [[0, 5], [1, 5], [2, 5], [12, 16], [12, 9],[13, 16], [20, 23], [29, 33], [30, 33]], 
 [[5, 7], [6, 8], [7, 9], [8, 10], [9, 11], [10, 12], [16, 18], [17, 19], [18, 20], [23, 25], [24, 26], [25, 27], [26, 28], [27, 29], [33, 35], [34, 36], [35, 37], [36, 38], [37, 39], [38, 40], [39, 41], [40, 42], [41, 43], [42, 44]]
]


d = defaultdict(list)
for k, v in l[-1]:
    d[k].append([[k,v]])

for sub in reversed(l[:-1]):
    ds = defaultdict(list)
    for k, v in sub:
        if v in d:
            ds[k].extend([[k,v], *v2] for v2 in d[v] )
    d = ds

list(chain.from_iterable(d.values()))

Вывод:

[[[7, 12], [12, 16], [16, 18]],
 [[7, 12], [12, 9], [9, 11]],
 [[6, 12], [12, 16], [16, 18]],
 [[6, 12], [12, 9], [9, 11]],
 [[25, 30], [30, 33], [33, 35]]]

Answer 2

Вы можете использовать itertools.product для итерации по всем возможным цепочкам (все комбинации по 1 диапазону от каждой "строки"),

, а затем отфильтровать их с помощью простой функции, которая проверяет, указанная c цепочка допустима.

попробуйте это:

from itertools import product

def check_chain(chain):
    prev_end = chain[0][1]
    for start, end in chain[1:]:
        if start != prev_end:
            return False
        prev_end = end
    return True

all_candidate_chains = product(*list)

result = [[*chain] for chain in all_candidate_chains if check_chain(chain)]

print(result)

Вывод:

[[[7, 12], [12, 16], [16, 18]], [[6, 12], [12, 16], [16, 18]], [[25, 30], [30, 33], [33, 35]]]

РЕДАКТИРОВАТЬ:

также можно использовать zip и all для замены check_chain на 1 вкладыш:

from itertools import product
result = [[*chain] for chain in product(*list) if all(end1 == start2 for (_, end1), (start2, _) in zip(chain, chain[1:]))]
print(result)