识别列表中连续数字的组

Question

我想在一个列表中找出连续的数字组，也就是说：

myfunc([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

返回的结果是：

[(2,5), (12,17), 20]

我在想，怎么做这个比较好，特别是Python里面有没有现成的方法可以用。

补充说明：我最开始忘了提，单独的数字应该作为单独的数字返回，而不是作为一个范围。

Answer 1

我觉得这个“简单”的解决方案至少还算容易理解。

x = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 22, 25, 26, 28, 51, 52, 57]

def group(L):
    first = last = L[0]
    for n in L[1:]:
        if n - 1 == last: # Part of the group, bump the end
            last = n
        else: # Not part of the group, yield current group and start a new
            yield first, last
            first = last = n
    yield first, last # Yield the last group


>>>print list(group(x))
[(2, 5), (12, 17), (22, 22), (25, 26), (28, 28), (51, 52), (57, 57)]

Answer 2

编辑 2：为了回应提问者的新需求

ranges = []
for key, group in groupby(enumerate(data), lambda (index, item): index - item):
    group = map(itemgetter(1), group)
    if len(group) > 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])

输出：

[xrange(2, 5), xrange(12, 17), 20]

你可以把xrange换成range，或者其他自定义的类。

---

Python的文档里有一个很不错的示例，可以参考一下：

from operator import itemgetter
from itertools import groupby
data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    print(map(itemgetter(1), g))

输出：

[2, 3, 4, 5]
[12, 13, 14, 15, 16, 17]

如果你想得到完全一样的输出，可以这样做：

ranges = []
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    group = map(itemgetter(1), g)
    ranges.append((group[0], group[-1]))

输出：

[(2, 5), (12, 17)]

---

编辑：这个例子在文档里已经解释过了，但我觉得我可以再详细说一下：

解决这个问题的关键是用一个范围进行差分，这样连续的数字就会出现在同一组里。

如果数据是：[2, 3, 4, 5, 12, 13, 14, 15, 16, 17]，那么groupby(enumerate(data), lambda (i,x):i-x)就相当于下面的：

groupby(
    [(0, 2), (1, 3), (2, 4), (3, 5), (4, 12),
    (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)],
    lambda (i,x):i-x
)

这个lambda函数是把元素的索引减去元素的值。所以当你对每个项目应用这个lambda时，你会得到以下的分组键：

[-2, -2, -2, -2, -8, -8, -8, -8, -8, -8]

groupby是根据相同的键值来分组元素，所以前四个元素会被分到一起，依此类推。

希望这样能让你更容易理解。

python 3版本可能对初学者更有帮助。

首先导入所需的库

from itertools import groupby
from operator import itemgetter

ranges =[]

for k,g in groupby(enumerate(data),lambda x:x[0]-x[1]):
    group = (map(itemgetter(1),g))
    group = list(map(int,group))
    ranges.append((group[0],group[-1]))

Answer 3

more_itertools.consecutive_groups 是在4.0版本中新增的功能。

示例

import more_itertools as mit


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
[list(group) for group in mit.consecutive_groups(iterable)]
# [[2, 3, 4, 5], [12, 13, 14, 15, 16, 17], [20]]

代码

使用这个工具，我们可以创建一个生成器函数，来找到连续数字的范围。

def find_ranges(iterable):
    """Yield range of consecutive numbers."""
    for group in mit.consecutive_groups(iterable):
        group = list(group)
        if len(group) == 1:
            yield group[0]
        else:
            yield group[0], group[-1]


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
list(find_ranges(iterable))
# [(2, 5), (12, 17), 20]

这个源代码的实现模仿了一个经典的做法（由 @Nadia Alramli 展示）。

注意：more_itertools 是一个第三方包，可以通过pip install more_itertools来安装。