Найдите все возможные комбинации, которые перекрываются в конце и в начале

Question

В посте найдите все комбинации с неперекрывающимися областями (код вставлен ниже), функции дается набор кортежей, и она рекурсивно находит каждую возможную коллекцию кортежей с неперекрывающимися значениями. Например, в списке кортежей T = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)] мы получаем

def nonovl(l, idx, right, ll):
    if idx == len(l):
        if ll:
            print(ll)
        return

    next = idx + 1  
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    next = idx + 1
    right = l[idx][1]
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll + str(l[idx]))

>>> T = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)]
>>> l.sort()
>>> nonovl(l, 0, -1, "")
(6.0, 7.25)
(2.5, 4.5)
(2.5, 4.5)(6.0, 7.25)
(2.0, 5.75)
(2.0, 5.75)(6.0, 7.25)
(2.0, 4.0)
(2.0, 4.0)(6.0, 7.25)
(0.0, 4.0)
(0.0, 4.0)(6.0, 7.25)
(0.0, 2.0)
(0.0, 2.0)(6.0, 7.25)
(0.0, 2.0)(2.5, 4.5)
(0.0, 2.0)(2.5, 4.5)(6.0, 7.25)

Как мы можем изменить функцию nonovl(), чтобы она также учитывала комбинации, которые перекрываются при запуске и конечные значения двух кортежей? Например, запустив его в том же списке, мы также получим:

(0.0, 2.0)(2.0, 4.0)(6.0, 7.25)

Answer 1

Измените >= на >. Прямо сейчас код пропускает «следующий» кортеж, если значение левого индекса «следующего» кортежа меньше или равно правому значению индекса «текущего» кортеж. Он находит первый кортеж, значение левого индекса которого строго больше значения правого индекса текущего кортежа.

def nonovl(l, idx, right, ll):
    if idx == len(l):
        if ll:
            print(ll)
        return

    next = idx + 1  
    while next < len(l) and right > l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    next = idx + 1
    right = l[idx][1]
    while next < len(l) and right > l[next][0]:
        next += 1
    nonovl(l, next, right, ll + str(l[idx]))

Вывод:

(6.0, 7.25)
(2.5, 4.5)
(2.5, 4.5)(6.0, 7.25)
(2.0, 5.75)
(2.0, 5.75)(6.0, 7.25)
(2.0, 4.0)
(2.0, 4.0)(6.0, 7.25)
(0.0, 4.0)
(0.0, 4.0)(6.0, 7.25)
(0.0, 2.0)
(0.0, 2.0)(6.0, 7.25)
(0.0, 2.0)(2.5, 4.5)
(0.0, 2.0)(2.5, 4.5)(6.0, 7.25)
(0.0, 2.0)(2.0, 5.75)
(0.0, 2.0)(2.0, 5.75)(6.0, 7.25)
(0.0, 2.0)(2.0, 4.0)
(0.0, 2.0)(2.0, 4.0)(6.0, 7.25)