如何从跨距列表中获得所有最大的非重叠跨距集

Question

我似乎找不到一种在标题中编写算法的方法，而不需要以某种方式整理结果。在

为了说明我想要什么：

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]
]

我目前的实施或多或少是这样的：

^{pr2}$

但它产生了非最大跨距，我宁愿一开始就不想创建。在

>>> 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)]

有没有其他方法可以避免这种行为？我在“间隔重叠”和“活动调度”这两个关键词下发现了类似的问题，但它们似乎都没有提到这个特定的问题。在

Answer 1

假设范围按下界排序，我们希望将当前范围附加到它可以附加到的最长路径上，或者创建一个新路径（附加到空路径）。如果需要的话，我们可以考虑让搜索最长前缀的效率更高。（下面的代码只是用稍微优化的线性方法更新搜索。）

（我不知道如何使用yield功能，也许您可以让这段代码更优雅。）

# Assumes spans are sorted by lower bound
# and each tuple is a valid range
def f(spans):
  # Append the current span to the longest
  # paths it can be appended to.
  paths = [[spans.pop(0)]]
  for l,r in spans:
    to_extend = []
    longest = 0
    print "\nCandidate: %s" % ((l,r),)
    for path in paths:
      lp, rp = path[-1]
      print "Testing on %s" % ((lp,rp),)
      if lp <= l < rp:
        prefix = path[:-1]
        if len(prefix) >= longest:
          to_extend.append(prefix + [(l,r)])
          longest = len(prefix)
      # Otherwise, it's after so append it.
      else:
        print "Appending to path: %s" % path
        path.append((l, r))
        longest = len(path)
    for path in to_extend:
      print "Candidate extensions: %s" % to_extend
      if len(path) == longest + 1:
        print "Adding to total paths: %s" % path
        paths.append(path)

  print "\nResult: %s" % paths
  return paths

all_spans = [(0, 5), (2, 7), (5, 8), (6, 10), (9, 10), (11, 15)]

f(all_spans)

输出：

^{pr2}$

Answer 2

这取决于你不想策划结果是什么意思。在

使用生成器后，可以过滤掉非最大结果：

all_results = [s for s in combine(all_spans, set())]

for first_result in list(all_results):
    for second_result in list(all_results):
        if first_result.issubset(second_result) and first_result != second_result:
            all_results.remove(first_result)
            break

为了避免一开始就产生它们，你可以在让步之前做一个检查，看看答案是否最大。比如：

^{pr2}$

Answer 3

这是一个简单的（？）图形问题。制作一个有向图，其中每个跨度是一个节点。如果span B直到span A结束才开始，则存在边AB（从节点A到节点B）iff A[1]<；=B[0]。你的图表看起来像

Node    =>  Successors
(0, 5)  =>  (5, 8), (6, 10), (9, 10), (11, 15)
(2, 7)  =>  (9, 10), (11, 15)
(5, 8)  =>  (9, 10), (11, 15)
(6, 10) =>  (11, 15)
(9, 10) =>  (11, 15)

现在，问题简化为简单地找到通过图的最长路径，包括连接。在

考虑到问题的线性度，找到一个最大解比较容易：在每一步中，选择具有最快结束时间的后续节点。分步骤：

1. 首先，所有节点都可用。结束时间最快的是（0,5）。在
2. 最早结束的（0,5）的继承者是（5,8）。在
3. （5，8）的继承人。。。是（9，10）
4. 。。。最后加上（11，15）

请注意，这并不需要一个图；只需要一个您愿意通过第一个子元素或第二个子元素引用的结构。在

解的长度是4，你已经知道了。在

你能从这里取吗？在