如何从一个跨度列表中获取所有最大不重叠的跨度集合

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

我的当前实现大致如下:

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

是否有不同的方法可以避免这种行为？我在关键词“区间重叠”和“活动调度”下找到了类似的问题，但似乎没有一个涉及到这个特定的问题。

- Arne

---

“{(5, 8), (9, 10), (11, 15)}” 比 “{(2, 7), (9, 10), (11, 15)}” 更差，为什么？ - MBo

这并不是更糟，只是无效，因为有一个严格更大的集合： {(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

@MaartenFabré 像这个一样吗？它从所有跨度的列表开始，如果包含重叠，则尝试所有可能的较短版本。它可以被视为一个图形，其中每个叶子是一个有效的集合。它们也不是最小或唯一的，但也许可以改变。 - Arne

元素数量 - Arne

Answer 1

这取决于你所说的不想筛选结果的意思。

在使用生成器后，您可以通过以下方式过滤掉非最大结果：

Original Answer翻译成："最初的回答"

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

为了避免最初的回答，您可以在yield之前进行检查，看看答案是否是最大的。可以使用以下代码实现：

不要在最开始就生成它们，您可以在yield之前进行检查，看看答案是否是最大的。可以使用以下代码实现：

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])
    # Check whether the current set is maximal.
    possible_additions = set(spans)
    for item_to_consider in set(possible_additions):
        if any([has_overlap(item_in_current, item_to_consider) for item_in_current in current]):
            possible_additions.remove(item_to_consider)
    if len(possible_additions) == 0:
        yield current

- Andrew McDowell

---

假设 len(spans) = n 且 len(results) = m，第一种方法的清理复杂度为 *O(m*m)*，而第二种方法的预防复杂度为 *O(n*m*m)*，因此我会坚持使用第一种方法。 - Arne

@Arne（如果len(spans) = n and len(results) = m），我认为我的时间复杂度是O(n * m)。这个看起来对吗？ - גלעד ברקן

迟做总比不做好：我选择了过滤器方法，它产生了最干净的代码，并且在处理我需要处理的数据时表现最佳。 - Arne

Answer 2

这是一个简单的图问题。制作一个有向图，其中每个跨度都是一个节点。如果A的结束时间小于等于B的开始时间，则存在一条从节点A到节点B的边AB。你的图将如下所示：

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，这一点你已经知道了。

从这里开始你能做到吗？

- Prune

---

当然，我会尝试实现它（不过不是今天），如果遇到问题，我会回来的。感谢您的帖子 =) - Arne

Answer 3

假设范围按下限排序，我们想将当前范围附加到最长的可附加路径上，或创建新路径（附加到空路径）。如果需要，我们可以考虑使查找最长前缀更有效率。（下面的代码只是在稍微优化的线性方法中更新该搜索。）

（我不确定如何使用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)

输出：

"""
Candidate: (2, 7)
Testing on (0, 5)
Candidate extensions: [[(2, 7)]]
Adding to total paths: [(2, 7)]

Candidate: (5, 8)
Testing on (0, 5)
Appending to path: [(0, 5)]
Testing on (2, 7)

Candidate: (6, 10)
Testing on (5, 8)
Testing on (2, 7)
Candidate extensions: [[(0, 5), (6, 10)]]
Adding to total paths: [(0, 5), (6, 10)]

Candidate: (9, 10)
Testing on (5, 8)
Appending to path: [(0, 5), (5, 8)]
Testing on (2, 7)
Appending to path: [(2, 7)]
Testing on (6, 10)

Candidate: (11, 15)
Testing on (9, 10)
Appending to path: [(0, 5), (5, 8), (9, 10)]
Testing on (9, 10)
Appending to path: [(2, 7), (9, 10)]
Testing on (6, 10)
Appending to path: [(0, 5), (6, 10)]

Result: [[(0, 5), (5, 8), (9, 10), (11, 15)],
         [(2, 7), (9, 10), (11, 15)],
         [(0, 5), (6, 10), (11, 15)]]
"""

- גלעד ברקן