迭代Python中的范围列表中找不到的整数

Question

因此，我有一个函数，它输出一个范围列表，例如范围(1，5)，范围(8，13)。我需要迭代那些不在这个列表范围内的整数。例如，使用前面的列表，我希望能够在前面提到的列表中遍历5-7。

我将使用的列表和范围可能相当大(即整数从0到数百万)。

有没有办法做到这一点，而不将每个范围转换为一个数字列表，并使用如果不是在语句中？

Answer 1

使用Mark的模板：

r = [range(1,5), range(8,13), range(20, 25), range(22, 27),  range(30, 35)]

def missing(r):
    stop = r[0].stop
    for a in r:
        yield from range(stop, a.start)
        stop = max(stop, a.stop)
    
print(list(missing(r)))

输出：

[5, 6, 7, 13, 14, 15, 16, 17, 18, 19, 27, 28, 29]

Answer 2

迭代工具模块对这个问题做了简短的工作：

>>> from itertools import pairwise, chain
>>> excluded = [range(1,5), range(8,13), range(20, 30), range(34, 38)]
>>> included = [range(p.stop, q.start) for p, q in pairwise(excluded)]
>>> list(chain.from_iterable(included))
[5, 6, 7, 13, 14, 15, 16, 17, 18, 19, 30, 31, 32, 33]

为了便于阅读，我把它写成两个单独的步骤：

1. 将排除的范围转换为包含范围的列表。包含的范围是从上一个排除范围的停止和下一个排除范围的开始生成的。
2. 链接步骤将所有这些范围合并到一个迭代器中。

如果需要，可以将这些步骤合并为一个一行：

for i in chain.from_iterable(range(p.stop, q.start) for p, q in pairwise(excluded)):
    print(i)

编辑

在评论中，OP指出，输入可能比示例中显示的更复杂。下面是如何通过对输入进行排序和删除重叠范围来准备数据：

from operator import attrgetter

excluded = [range(23, 25), range(1,6), range(8,16), range(2, 5), range(22, 27),
            range(3, 4), range(20, 25), range(7, 15), range(30, 35)]

pairs = sorted(map(attrgetter('start', 'stop'), excluded))
non_overlapping = []
start = None
for pair in pairs:
    if start is None:
        start, stop = pair
        continue
    next_start, next_stop = pair
    if next_start >= stop:
        non_overlapping.append((start, stop))
        start, stop = next_start, next_stop
        continue
    stop = max(stop, next_stop)
if start is not None:
    non_overlapping.append((start, stop))

Answer 3

您可以从范围的停止和开始处压缩对并创建新的范围。如果存在像range(20, 25), range(22, 27)这样的重叠，这将有效，但如果某些范围完全包含在其他范围(如range(10, 20), range(12, 15))中，则不会。如果后者是可能的，则需要添加一些逻辑来忽略所包含的范围。

r = [range(1,5), range(8,13), range(20, 25), range(22, 27),  range(30, 35)]

def missing(r):
    g = (range(a.stop,  b.start) for a, b in zip(r, r[1:]))
    for interval in g:
         yield from interval

list(missing(r))
# [5, 6, 7, 13, 14, 15, 16, 17, 18, 19, 27, 28, 29]

对于一个范围完全重叠的更复杂的场景，可以忽略包含的范围，如下所示：

r = [range(1,5), range(2, 4), range(8,13), range(20, 25), range(22, 27), range(23, 25), range(30, 35)]

def missing(r):
    current = r[0]
    for next_range in r[1:]:
        if next_range.stop < current.stop:
            continue
        yield from range(current.stop, next_range.start)
        current = next_range
            
list(missing(r))
# [5, 6, 7, 13, 14, 15, 16, 17, 18, 19, 27, 28, 29]

这忽略了包含在range(2, 4)中的范围(如range(1, 5) )。