我似乎找不到一种方法能够不需要以某种方式筛选结果就能编写标题中的算法。
以下是我的要求:
all_spans = [(0, 5), (2, 7), (5, 8), (6, 10), (9, 10), (11, 15)]
possible_sets = [
{(0, 5), (5, 8), (9, 10), (11, 15)},
{(2, 7), (9, 10), (11, 15)},
{(0, 5), (6, 10), (11, 15)}
]
not_possible = [
{(0, 5), (5, 8), (6, 10), (11, 15)}, # has overlaps
{(5, 8), (9, 10), (11, 15)} # not maximal w.r.t possible_sets[0]
]
我的当前实现大致如下:
def has_overlap(a, b):
return a[1] > b[0] and b[1] > a[0]
def combine(spans, current, idx=0):
for i in range(idx, len(spans)):
overlaps = {e for e in current if has_overlap(e, spans[i])}
if overlaps:
yield from combine(spans, current-overlaps, i)
else:
current.add(spans[i])
yield current
但它会生成我不想要的非最大跨度。
>>> for s in combine(all_spans, set()):
... print(sorted(s))
[(9, 10), (11, 15)]
[(6, 10), (11, 15)]
[(5, 8), (9, 10), (11, 15)]
[(9, 10), (11, 15)]
[(6, 10), (11, 15)]
[(2, 7), (9, 10), (11, 15)]
[(0, 5), (9, 10), (11, 15)]
[(0, 5), (6, 10), (11, 15)]
[(0, 5), (5, 8), (9, 10), (11, 15)]
是否有不同的方法可以避免这种行为?我在关键词“区间重叠”和“活动调度”下找到了类似的问题,但似乎没有一个涉及到这个特定的问题。
{(0, 5), (5, 8), (9, 10), (11, 15)}
。对于{(2, 7),(9, 10),(11, 15)}
,没有这样严格更大的有效集合。 - Arne{(0, 5), (9, 10), (11, 15)}
不也是非最大的吗?它似乎是{(0, 5), (5, 8), (9, 10), (11, 15)}
的子集。 - Andrew McDowell