我有一个整数区间，它包含一些内部区间。给定这些间隔，我想计算一个列表，包括

Question

内部间隔总是在全局间隔内。所有的间隔都是整数的，左闭的，右开的.

以这个例子为例。“全局”间隔为[0，22]。“内部”间隔为[3，6[和[12，15]]。

对于这个例子，我期望：[0，3][U [3，6][U [6，12]]U [12，15]U [15，22]

我尝试过定义一个函数，但是在迭代间隔时，我却弄乱了索引。

def allspans(r, spans):
    pass

allspans((0, 22), [(3,6), (12,15)])  # expected : [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Answer 1

是的，您必须迭代您的spans，但是要注意保持一个位置，以正确地填充中间的空格。

from typing import Generator

def allspans(r, spans) -> Generator:
    pos = 0
    for lower, upper in spans:
        if pos < lower:
            yield pos, lower
        yield lower, upper
        pos = upper
    if pos <= r[1]:
        yield pos, r[1]

我发现使用Generator更容易。只需使用list()将其转换为List。

list(allspans((0, 22), [(3,6), (12,15)]))  # [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Answer 2

使用普通循环：

def allspans(r, spans):
    intervals = []
    intervals.append((r[0], spans[0][0]))

    for i in range(len(spans)):
        current_span = spans[i]
        if i != 0:
            intervals.append((spans[i - 1][1], current_span[0]))
        intervals.append((current_span[0], current_span[1]))

    intervals.append((spans[-1][1], r[1]))

    return intervals


print(allspans((0, 22), [(3, 6), (12, 15)]))
# [(0, 3), (3, 6), (6, 12), (12, 15), (15, 22)]

Answer 3

使用itertools.chain和itertools.pairwise (Python3.10+)：

from itertools import chain, pairwise

def all_spans(r, spans):
    start, end = r
    it = chain((start,), chain.from_iterable(spans), (end,))
    return [t for t in pairwise(it) if t[0] != t[1]] 

首先，我们按照顺序在所有区间端点上构造一个迭代器it；然后子范围是所有连续端点的对，不包括两个连续端点相等的空子范围。