在列表中查找数字簇

Question

我正在努力解决这个问题,因为我确信十几个for循环不是这个问题的解决方案:

有一个排序的数字列表,如

numbers = [123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430]

我想创建一个带有数字列表的字典,其中数字的差异(彼此跟随)不超过15.所以输出将是这样的:

clusters = {
    1 : [123, 124, 128],
    2 : [160, 167],
    3 : [213, 215, 230, 245, 255, 257],
    4 : [400, 401, 402],
    5 : [430]
}

我目前的解决方案有点难看(我必须在最后删除重复...),我确信它可以用pythonic方式完成.

这就是我现在所做的:

clusters = {}  
dIndex = 0 
for i in range(len(numbers)-1) :
    if numbers[i+1] - numbers[i] <= 15 :
        if not clusters.has_key(dIndex) : clusters[dIndex] = []
        clusters[dIndex].append(numbers[i])
        clusters[dIndex].append(numbers[i+1])
    else : dIndex += 1

Answer 1

如果您的列表很小,则不是绝对必要的,但我可能会以"流处理"方式处理此问题:定义一个生成器,使您的输入可迭代,并将元素分组为不同的数字<= 15的元素.然后您可以使用它轻松生成您的字典.

def grouper(iterable):
    prev = None
    group = []
    for item in iterable:
        if not prev or item - prev <= 15:
            group.append(item)
        else:
            yield group
            group = [item]
        prev = item
    if group:
        yield group

numbers = [123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430]
dict(enumerate(grouper(numbers), 1))

打印:

{1: [123, 124, 128],
 2: [160, 167],
 3: [213, 215, 230, 245, 255, 257],
 4: [400, 401, 402],
 5: [430]}

作为奖励,这使您甚至可以将运行分组为潜在无限列表(当然,只要它们已经排序).您还可以将索引生成部分粘贴到生成器本身(而不是使用enumerate)作为次要增强.

Answer 2

import itertools
import numpy as np

numbers = np.array([123, 124, 128, 160, 167, 213, 215, 230, 245, 255, 257, 400, 401, 402, 430])
nd = [0] + list(np.where(np.diff(numbers) > 15)[0] + 1) + [len(numbers)]

a, b = itertools.tee(nd)
next(b, None)
res = {}
for j, (f, b) in enumerate(itertools.izip(a, b)):
    res[j] = numbers[f:b]

如果您可以使用 itertools 和 numpy。适应pairwise迭代器技巧。在+1需要的指数移动，添加0和len(numbers)榜上有名确保使第一和最后一个项正确地包括在内。

你显然可以不用 out 来做到这一点itertools，但我喜欢tee。