найти все комбинации с неперекрытыми регионами - PullRequest
Новая
       28

найти все комбинации с неперекрытыми регионами

0 голосов
/ 06 ноября 2018

В пределах суперрегиона S имеется k небольших субрегионов. Число k может быть до 200. Может быть совпадение между субрегионами. У меня миллионы регионов S.

Для каждого суперрегиона моя цель - найти все комбинации, в которых есть 2 или более непересекающихся субрегиона.

Вот пример:

Супер регион: 1-100

Субрегионы: 1-8, 2-13, 9-18, 15-30, 20-35

Цель:

Комбинация1: 1-8, 9-18

Комбинация2: 1-8, 20-35

Комбинация3: 1-8, 9-18, 20-35

Комбинация 4: 1-8, 15-30

...

1 Ответ

0 голосов
/ 06 ноября 2018

Количество подмножеств может быть экспоненциальным (максимум 2 ^ k), поэтому нет ничего плохого в том, чтобы пройти все возможные независимые подмножества с помощью рекурсии. Я использовал линейный поиск следующего возможного интервала, но стоит использовать бинарный поиск. 

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

    #find next non-overlapping interval without using l[idx]
    next = idx + 1  
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    #find next non-overlapping interval after using l[idx]
    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]))

l=[(1,8),(2,13),(9,18),(15,30),(20,35)]
l.sort()
nonovl(l, 0, -1, "")

(20, 35)
(15, 30)
(9, 18)
(9, 18)(20, 35)
(2, 13)
(2, 13)(20, 35)
(2, 13)(15, 30)
(1, 8)
(1, 8)(20, 35)
(1, 8)(15, 30)
(1, 8)(9, 18)
(1, 8)(9, 18)(20, 35)
...