在至少三个范围之间寻找范围重叠Python

Question

我有一个元组列表，我用它来标记范围的上下限。例如：

[(3,10), (4,11), (2,6), (8,11), (9,11)] # 5 separate ranges.

我想找到三个或更多输入范围重叠的范围。例如，上面列出的元组将返回：

^{pr2}$

我尝试了@WolframH提供的方法来回答这个post

但我不知道我能做些什么：

• 给我一个以上的输出范围

• 设置至少三个范围重叠的阈值以限定输出

Answer 1

当然，如果你想的话，你可以通过强力检查所有的组合来解决这个问题。如果你需要这个算法来缩放，你可以用（伪）nlogn来实现。从技术上讲，你可以得到一个退化的最坏情况是O（n**2），但这是什么呢。在

基本上，你对范围进行排序，然后对于一个给定的范围，你看它的左上角的边界是否重叠，如果是这样的话，你就把重叠的间隔标记为结果。伪代码（实际上几乎是有效的python，看看这个）：

ranges.sort()

for left_range, current_range, right_range in sliding_window(ranges, 3):
  if left_range.right < current_range.left:
    continue
  while right_range.left < min(left_range.right, current_range.right):
      results.append(overlap(left_range, right_range))
      right_range = right_range.next
  #Before moving on to the next node, extend the current_range's right bound
  #to be the longer of (left_range.right, current_range.right)
  #This makes sense if you think about it.
  current_range.right = max(left_range.right, current_range.right)

merge_overlapping(results)

（您还需要在末尾合并一些可能重叠的范围，这是另一个nlogn操作-尽管n在那里通常要小得多。我将不讨论这方面的代码，但它与上面的方法类似，涉及排序然后合并。See here for an example。）

Answer 2

你首先要找到所有范围的组合。然后可以将它们转换为集合并计算交集：

import itertools


limits = [(3,10), (4,11), (2,6), (8,11), (9,11)]
ranges = [range(*lim) for lim in  limits]

results = []
for comb in itertools.combinations(ranges,3):
    intersection = set(comb[0]).intersection(comb[1])
    intersection = intersection.intersection(comb[2])
    if intersection and intersection not in results and\
       not any(map(intersection.issubset, results)):
        results = filter(lambda res: not intersection.issuperset(res),results)
        results.append(intersection)


result_limits =  [(res[0], res[-1]+1) for res in map(list,results)]

它应该给你所有的三向交叉路口