查找具有非重叠区域的所有组合 [英] find all combinations with non-overlapped regions

问题描述

在超区域S中，有k个小子区域.数字k最多可以为200.子区域之间可能有重叠.我有数百万个地区S.

Within a super-region S, there are k small subregions. The number k can be up to 200. There may be overlap between subregions. I have millions of regions S.

对于每个超级区域，我的目标是找出其中有2个或更多不重叠子区域的所有组合.

For each super-region, my goal is to find out all combinations in which there are 2 or more non-overlapped subregions.

这里是一个示例:

超级区域:1-100

Super region: 1-100

子区域:1-8、2-13、9-18、15-30、20-35

Subregions: 1-8, 2-13, 9-18, 15-30, 20-35

目标:

组合1:1-8、9-18

Combination1: 1-8, 9-18

组合2:1-8、20-35

Combination2: 1-8, 20-35

组合3:1-8、9-18、20-35

Combination3: 1-8, 9-18, 20-35

组合4:1-8、15-30

Combination4: 1-8, 15-30

...

推荐答案

子集的数量可能是指数的(最大2 ^ k)，因此以递归方式遍历所有可能的独立子集是没有错的.我已经对下一个可能的时间间隔进行了线性搜索，但是值得利用二进制搜索.

Number of subsets might be exponential (max 2^k), so there is nothing wrong to traverse all possible independent subsets with recursion. I've used linear search of the next possible interval, but it is worth to exploit binary search.

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)

这篇关于查找具有非重叠区域的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！