遍历 Python 范围列表中未找到的整数

Question

所以，我有一个输出范围列表的函数，例如[范围（1,5），范围（8,13）]。我需要遍历那些不在这个列表范围内的整数。例如，使用前面的列表，我希望能够遍历前面提到的列表中的 5-7。

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

有没有办法在不将每个范围转换为数字列表并使用 if not in 语句的情况下执行此操作？

Answer 1

您可以压缩对并从范围的停止和开始创建新的范围。如果存在像 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(1, 5) 中包含的 range(2, 4) 等范围。

Answer 2

使用马克的模板：

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 3

itertools module 简化了这个问题：

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

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

将排除范围转换为包含范围列表。包含范围是从上一个排除范围的 stop 和下一个排除范围的 start 构建的。
链接步骤将所有这些范围合并到一个迭代器中。

如果需要，可以将这些步骤合并在一起以形成 one-liner:

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

遍历 Python 范围列表中未找到的整数

Iterating through integers not found in a list of ranges in Python

python

list

loops

range

itertools