找到具有非重叠区域的所有组合
find all combinations with non-overlapped regions
在一个超区域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
...
子集的数量可能是指数级的(最大 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)
在一个超区域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
...
子集的数量可能是指数级的(最大 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)