识别列表中的连续数字组

Question

我想在列表中标识连续数字组,以便:

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

返回:

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

并且想知道最好的方法是什么(特别是如果在Python中有内置的东西).

编辑:注意我原本忘了提到个别数字应该作为单独的数字返回,而不是范围.

Answer 1

编辑2:回答OP新要求

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.

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时.您将获得groupby的以下键:

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

groupby通过相等的键值对元素进行分组,因此前4个元素将组合在一起,依此类推.

我希望这会让它更具可读性.

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 2

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.

Answer 3

"天真"的解决方案,我发现至少有些可读.

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 4

假设您的列表已排序:

>>> from itertools import groupby
>>> def ranges(lst):
    pos = (j - i for i, j in enumerate(lst))
    t = 0
    for i, els in groupby(pos):
        l = len(list(els))
        el = lst[t]
        t += l
        yield range(el, el+l)


>>> lst = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
>>> list(ranges(lst))
[range(2, 6), range(12, 18)]

Answer 5

这是应该工作的东西,不需要任何导入:

def myfunc(lst):
    ret = []
    a = b = lst[0]                           # a and b are range's bounds

    for el in lst[1:]:
        if el == b+1: 
            b = el                           # range grows
        else:                                # range ended
            ret.append(a if a==b else (a,b)) # is a single or a range?
            a = b = el                       # let's start again with a single
    ret.append(a if a==b else (a,b))         # corner case for last single/range
    return ret

Answer 6

请注意,使用的代码groupby不能像Python 3中那样工作,所以请使用它.

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