Identify groups of continuous numbers in a list

这不使用标准函数-它只是遍历输入，但它应该可以工作:

def myfunc(l):
r = []
p = q = None
for x in l + [-1]:
if x - 1 == q:
q += 1
else:
if p:
if q > p:
r.append('%s-%s' % (p, q))
else:
r.append(str(p))
p = q = x
return '(%s)' % ', '.join(r)

注意，它要求输入只包含升序的正数。您应该验证输入，但为了清楚起见，省略了这段代码。

Assuming your list is sorted:

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

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

可以用 range 或任何其他自定义类替换 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))

Output:

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

output:

[(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个元素将被分组在一起，依此类推。

I hope this makes it more readable.

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

这个“天真”的解决方案至少让我觉得有点可读性。

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

这是我想到的答案。我编写的代码是为了让其他人能够理解，所以我对变量名和注释相当详细。

首先是一个快速帮助函数:

def getpreviousitem(mylist,myitem):
'''Given a list and an item, return previous item in list'''
for position, item in enumerate(mylist):
if item == myitem:
# First item has no previous item
if position == 0:
return None
# Return previous item
return mylist[position-1]

And then the actual code:

def getranges(cpulist):
'''Given a sorted list of numbers, return a list of ranges'''
rangelist = []
inrange = False
for item in cpulist:
previousitem = getpreviousitem(cpulist,item)
if previousitem == item - 1:
# We're in a range
if inrange == True:
# It's an existing range - change the end to the current item
newrange[1] = item
else:
# We've found a new range.
newrange = [item-1,item]
# Update to show we are now in a range
inrange = True
else:
# We were in a range but now it just ended
if inrange == True:
# Save the old range
rangelist.append(newrange)
# Update to show we're no longer in a range
inrange = False
# Add the final range found to our list
if inrange == True:
rangelist.append(newrange)
return rangelist

示例运行:

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

报税表:

[[2, 5], [12, 17]]

这里有一些应该会奏效的东西，不需要任何重要性:

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

Please note that the code using groupby doesn't work as given in Python 3 so use this.

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

import numpy as np


myarray = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
sequences = np.split(myarray, np.array(np.where(np.diff(myarray) > 1)[0]) + 1)
l = []
for s in sequences:
if len(s) > 1:
l.append((np.min(s), np.max(s)))
else:
l.append(s[0])
print(l)

产出:

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

在版本4.0中添加了 more_itertools.consecutive_groups 。

演示

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 所示)。

Note: more_itertools is a third-party package installable via pip install more_itertools.

使用 numpy + 理解列表:
利用数阶差分函数，可以识别出它们之间的差异不等于一的输入向量项。需要考虑输入向量的开始和结束。

import numpy as np
data = np.array([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])


d = [i for i, df in enumerate(np.diff(data)) if df!= 1]
d = np.hstack([-1, d, len(data)-1])  # add first and last elements
d = np.vstack([d[:-1]+1, d[1:]]).T


print(data[d])

产出:

 [[ 2  5]
[12 17]
[20 20]]

注意: 省略了对个别号码应区别对待的要求(以个别方式返回，而非范围)。这可以通过进一步的后处理结果来实现。通常情况下，这会使事情变得更加复杂，而不会带来任何好处。

一个不需要额外导入的简短解决方案。它接受任何可迭代的输入，对未排序的输入进行排序，并删除重复的项:

def ranges(nums):
nums = sorted(set(nums))
gaps = [[s, e] for s, e in zip(nums, nums[1:]) if s+1 < e]
edges = iter(nums[:1] + sum(gaps, []) + nums[-1:])
return list(zip(edges, edges))

例如:

>>> ranges([2, 3, 4, 7, 8, 9, 15])
[(2, 4), (7, 9), (15, 15)]


>>> ranges([-1, 0, 1, 2, 3, 12, 13, 15, 100])
[(-1, 3), (12, 13), (15, 15), (100, 100)]


>>> ranges(range(100))
[(0, 99)]


>>> ranges([0])
[(0, 0)]


>>> ranges([])
[]

This is the same as @dansalmo's 解决方案 which I found amazing, albeit a bit hard to read and apply (as it's not given as a function).

注意，通过修改 return 语句，可以很容易地将“传统的”开放范围 [start, end)修改为:

    return [(s, e+1) for s, e in zip(edges, edges)]

我从 另一个问题复制了这个答案，这个答案被标记为这个答案的副本，目的是让它更容易找到(在我刚刚再次搜索这个主题后，首先只找到这里的问题，并不满意给出的答案)。

使用 itertools中的 groupby和 count给我们提供了一个简短的解决方案。其思想是，在一个递增的序列中，指数和值之间的差值将保持不变。

为了跟踪索引，我们可以使用 Itertools.count，这使得代码像使用 enumerate一样简洁:

from itertools import groupby, count


def intervals(data):
out = []
counter = count()


for key, group in groupby(data, key = lambda x: x-next(counter)):
block = list(group)
out.append([block[0], block[-1]])
return out

一些样本输出:

print(intervals([0, 1, 3, 4, 6]))
# [[0, 1], [3, 4], [6, 6]]


print(intervals([2, 3, 4, 5]))
# [[2, 5]]

马克 · 拜尔斯、 Andrea Ambu、 沉默的幽灵、 Nadia Alramli和 truppo的版本简单快速。“ truppo”版本鼓励我编写一个版本，在处理步长1以外的步长时保留相同的灵活行为(并列出单例元素，在给定的步长下不会扩展超过1个步长)。它被赋予 给你。

>>> list(ranges([1,2,3,4,3,2,1,3,5,7,11,1,2,3]))
[(1, 4, 1), (3, 1, -1), (3, 7, 2), 11, (1, 3, 1)]

这不是最好的方法，但这是我的两分钱

def getConsecutiveValues2(arr):
x = ""
final = []
end = 0
start = 0
for i in range(1,len(arr)) :
if arr[i] - arr[i-1] == 1 :
end = i
else :
print(start,end)
final.append(arr[start:end+1])
start = i
if i == len(arr) - 1 :
final.append(arr[start:end+1])
return final


x = [1,2,3,5,6,8,9,10,11,12]
print(getConsecutiveValues2(x))


>> [[1, 2, 3], [5, 6], [8, 9, 10, 11]]

我认为这种方法比我在这里看到的任何答案都要简单(编辑: 根据 Plestry 的评论修改) :

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


starts = [x for x in data if x-1 not in data and x+1 in data]
ends = [x for x in data if x-1 in data and x+1 not in data and x not in starts]
singles = [x for x in data if x-1 not in data and x+1 not in data]
list(zip(starts, ends)) + singles

产出:

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

编辑:

如@dog 所说，这是 O (n * * 2)。提高性能的一个选项是将原始列表转换为集合(并将开始列表转换为集合) ，即。

data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
data_as_set = set(data)


starts = [x for x in data_as_set if x-1 not in data_as_set and x+1 in data_as_set]
startset = set(starts)
ends = [x for x in data_as_set if x-1 in data_as_set and x+1 not in data_as_set and x not in startset]
singles = [x for x in data_as_set if x-1 not in data_as_set and x+1 not in data_as_set]


print(list(zip(starts, ends)) + singles)

此实现适用于常规或非常规步骤

我需要达到同样的事情，但有细微的差别，步骤可以是不规则的。这是我的实施方案

def ranges(l):
if not len(l):
return range(0,0)
elif len(l)==1:
return range(l[0],l[0]+1)
# get steps
sl    = sorted(l)
steps = [i-j for i,j in zip(sl[1:],sl[:-1])]
# get unique steps indexes range
groups = [[0,0,steps[0]],]
for i,s in enumerate(steps):
if s==groups[-1][-1]:
groups[-1][1] = i+1
else:
groups.append( [i+1,i+1,s] )
g2 = groups[-2]
if g2[0]==g2[1]:
if sl[i+1]-sl[i]==s:
_=groups.pop(-2)
groups[-1][0] = i
# create list of ranges
return [range(sl[i],sl[j]+s,s) if s!=0 else [sl[i]]*(j+1-i) for i,j,s in groups]

举个例子

from timeit import timeit


# for regular ranges
l = list(range(1000000))
ranges(l)
>>> [range(0, 1000000)]
l = list(range(10)) + list(range(20,25)) + [1,2,3]
ranges(l)
>>> [range(0, 2), range(1, 3), range(2, 4), range(3, 10), range(20, 25)]
sorted(l);[list(i) for i in ranges(l)]
>>> [0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 20, 21, 22, 23, 24]
>>> [[0, 1], [1, 2], [2, 3], [3, 4, 5, 6, 7, 8, 9], [20, 21, 22, 23, 24]]


# for irregular steps list
l = [1, 3, 5, 7, 10, 11, 12, 100, 200, 300, 400, 60, 99, 4000,4001]
ranges(l)
>>> [range(1, 9, 2), range(10, 13), range(60, 138, 39), range(100, 500, 100), range(4000, 4002)]


## Speed test
timeit("ranges(l)","from __main__ import ranges,l", number=1000)/1000
>>> 9.303160999934334e-06

这是我试图优先考虑可读性的方法。注意，如果组中只有一个值，它将返回相同值的元组。这可以在我将发布的第二个代码片段中轻松修复。

def group(values):
"""return the first and last value of each continuous set in a list of sorted values"""


values = sorted(values)
first = last = values[0]


for index in values[1:]:
if index - last > 1:  # triggered if in a new group
yield first, last


first = index  # update first only if in a new group


last = index  # update last on every iteration


yield first, last  # this is needed to yield the last set of numbers

以下是一项测试的结果:

values = [0, 5, 6, 7, 12, 13, 21, 22, 23, 24, 25, 26, 30, 44, 45, 50]
result = list(group(values))
print(result)

结果 = [(0, 0), (5, 7), (12, 13), (21, 26), (30, 30), (44, 45), (50, 50)]

如果对于组中的单个值，您只想返回一个值，那么只需在收益率中添加一个条件检查:

def group(values):
"""return the first and last value of each continuous set in a list of sorted values"""


values = sorted(values)


first = last = values[0]


for index in values[1:]:
if index - last > 1:  # triggered if in a new group
if first == last:
yield first


else:
yield first, last


first = index  # update first only if in a new group


last = index  # update last on every iteration


if first == last:
yield first


else:
yield first, last

结果 = [0, (5, 7), (12, 13), (21, 26), 30, (44, 45), 50]

Python 2.7中的一行程序(如果感兴趣) :

x = [2, 3, 6, 7, 8, 14, 15, 19, 20, 21]


d = iter(x[:1] + sum(([i1, i2] for i1, i2 in zip(x, x[1:] + x[:1]) if i2 != i1+1), []))


print zip(d, d)


>>> [(2, 3), (6, 8), (14, 15), (19, 21)]

如果你希望你的输入是一个集合，还有另一个解决方案:

def group_years(years):
consecutive_years = []
for year in years:
close = {y for y in years if abs(y - year) == 1}
for group in consecutive_years:
if len(close.intersection(group)):
group |= close
break
else:
consecutive_years.append({year, *close})
  

return consecutive_years

例如:

group_years({2016, 2017, 2019, 2020, 2022})
Out[54]: [{2016, 2017}, {2019, 2020}, {2022}]