python - 多个范围列表的交集和补集

Question

我有一个这样的问题:我有多个间隔列表，现在我想获得它的所有可能的交集和补集。例如，如果有 2 个列表:

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 18], [20, 24]]

The output should be
output_a = [[0, 1], [1, 2], [5, 8], [8, 10], [13, 15], [15, 18], [18, 20], [20, 23], [24, 25]]
output_b = [[1, 2], [2, 5], [8, 10], [10, 12], [15, 18], [20, 23], [23, 24]]

n 个列表依此类推

可视化:

    List_a           |-----------|     |----------|
    List_b                  |------------|   |-------|
    List_c           |---------|     |------------|

       Set           |------|--|-|---|-|-|---|----|--|

  Output_a           |------|--|-|     |-|---|----|
  Output_b                  |--|-|---|-|-|   |----|--|
  Output_c           |------|--|     |-|-|---|----|

我使用 Python set() 的伪代码

Get all (start, end) of all intervals in all list into a set()
for each list:
    for intervals in list:
        for each element in set:
            if element in intervals:
                ->store element in dict

但这似乎不够高效和优雅，因为它需要 3 个 for 循环

您能为这种情况建议一个更好的算法吗？非常感谢

Answer 1

(注意:我没有完全理解这个问题以及如何组成 output_a 和 output_b。在这个“解决方案”中，我将提供构建使用我开发的库进行砖 block ，我希望它有所帮助，但请记住，此“解决方案”的输出与您提供的内容不完全匹配!)

我是 portion 的维护者，一个 Python 库，提供区间(和区间集)的数据结构和操作。该库特别支持间隔的自动简化，这会导致与建议的输出不同的输出。

让我们导入库并定义您的列表:

>>> import portion as P
>>> a = [[0, 2], [5, 10], [13, 23], [24, 25]]
>>> b = [[1, 5], [8, 12], [15, 18], [20, 24]]

现在我们将这些列表转换为间隔(析取):

>>> a = P.Interval(*[P.closed(x, y) for x, y in a])
>>> b = P.Interval(*[P.closed(x, y) for x, y in b])
>>> a
[0,2] | [5,10] | [13,23] | [24,25]
>>> b
[1,5] | [8,12] | [15,18] | [20,24]

让我们计算交集及其补集:

>>> intersection = a & b
>>> complement = ~intersection
>>> intersection
[1,2] | [5] | [8,10] | [15,18] | [20,23] | [24]
>>> complement
(-inf,1) | (2,5) | (5,8) | (10,15) | (18,20) | (23,24) | (24,+inf)

由于您不关心无穷大，因此我们将补码限制在 a 和 b 的范围内。为此，我们将 a | 包围起来。 b(包围体是包含给定间隔的最小原子间隔):

>>> (a | b).enclosure
[0,25]
>>> complement = complement & (a | b).enclosure
>>> complement
[0,1) | (2,5) | (5,8) | (10,15) | (18,20) | (23,24) | (24,25]

基于交集和补，你有所有可能的“断点”(及其“起源”)。