将连续整数分组并容忍1的间隙

Question

在Python中,给定一个排序整数列表,我会按连续值对它们进行分组,并容忍1的间隙.

例如,给出一个列表my_list:

In [66]: my_list
Out[66]: [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20]

我想要以下输出:

[[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]]

现在,如果我不必忍受1的差距,我可以应用这里解释的整洁解决方案:

import itertools
import operator
results = []
for k, g in itertools.groupby(enumerate(my_list), lambda (i,x):i-x):
        group = map(operator.itemgetter(1), g)
        results.append(group)

有没有办法将我的额外要求纳入上述解决方案？如果没有,解决问题的最佳方法是什么？

Answer 1

如有疑问,您可以随时编写自己的发电机:

def group_runs(li,tolerance=2):
    out = []
    last = li[0]
    for x in li:
        if x-last > tolerance:
            yield out
            out = []
        out.append(x)
        last = x
    yield out

演示:

list(group_runs(my_list))
Out[48]: [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]]

Answer 2

Numpy是一个非常有用的工具,并不是很难学.

O(n)只需一行代码就可以解决这个问题(不包括导入,数据和转换为列表 - 如果你真的需要它):

from numpy import array, diff, where, split
l= [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20]
result= split(l, where(diff(l)>2)[0]+1 )
print map(list, result)

更重要的是,如果您需要处理大型列表,代码非常快,与纯python解决方案不同

Answer 3

请记住，groupby 本身非常蹩脚。实力itertools.groupby是关键。对于这个特定问题，您需要创建一个带有内存的适当密钥（无状态密钥在这里不起作用）。

执行

class Key(object):
    def __init__(self, diff):
        self.diff, self.flag, self.prev = diff, [0,1], None
    def __call__(self, elem):
        if self.prev and abs(self.prev - elem) > self.diff:
            self.flag = self.flag[::-1]
        self.prev= elem
        return self.flag[0]

目的

[list(g) for k, g in groupby(my_list, key = Key(2))]
[[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]]

这个怎么运作

每次需要创建一个新的子列表 ( curr - prev > threshold) 时，您都需要切换一个标志。有多种方法可以切换标志

• flag = 1; flag *= -1
• flag = [0, 1 ]; flag = flag[::-1]
• flag = 0; flag = 0 if flag else 1

选择你心中所抗争的

因此，这会生成一个随附的密钥以及您的列表

[0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20]
[0, 0, 0, 0, 0, 0, 1,  1,  0,  0,  0,  0 , 0]
             <------>  <------>
          Toggle flag  Toggle flag
          0 -> 1, as   1 -> 0, as
          10 - 6 > 2   15 - 11 > 2

现在 as itertools.groupby，将具有相同键的连续元素分组，所有具有连续0s 或1s 的键的元素都被分组在一起

[0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20]
[0, 0, 0, 0, 0, 0, 1,  1,  0,  0,  0,  0 , 0]

[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]
[0, 0, 0, 0, 0, 0], [1,  1],  [0,  0,  0,  0 , 0]

你的最终结果是

[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]