Znalezienie klastrów numerów na liście

Question

jestem zmaga się z tym, ponieważ jestem pewien, że za kilkanaście-pętli nie jest rozwiązaniem dla tego problemu:

Jest uporządkowany wykaz numerów jak

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

i chcę utworzyć dict z listy numerów, przy czym różnica liczb (po siebie) wynosi nie więcej niż 15. Więc wyjście byłoby to:

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

Mój obecny solutio n jest nieco brzydki (muszę usunąć duplikaty na końcu ...), jestem pewien, że można to zrobić w sposób pytonowy.

To jest to, co robię teraz:

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

Nie jest to bezwzględnie konieczne, jeśli twoja lista jest niewielka, ale prawdopodobnie podchodzę do tego w sposób "przetwarzania strumieniowego": zdefiniuj generator, który przenosi twoje dane wejściowe, i zgrupowanie elementów w liczby liczb różniące się od < = 15. Następnie możesz go użyć do łatwego wygenerowania słownika.

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

drukuje:

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

Jako bonus, to pozwala nawet grupować trwa potencjalnie nieskończonych list (tak długo, jak są one sortowane, oczywiście). Można również przykleić część generującą indeks do samego generatora (zamiast używać enumerate) jako nieznacznego rozszerzenia.

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] 

Jeśli można użyć itertools i numpy. Dostosowano pairwise dla trików iteratora. Numer +1 jest potrzebny do przesunięcia indeksu, dodając do listy 0 i len(numbers), upewniając się, że pierwsze i ostatnie wpisy są zawarte poprawnie.

Możesz oczywiście zrobić to bez itertools, ale lubię tee.

Answer 3

Korzystanie z generatora, aby oddzielić logikę: (jedna funkcja nie jedno)

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

def cut_indices(numbers): 
    # this function iterate over the indices that need to be 'cut' 
    for i in xrange(len(numbers)-1): 
     if numbers[i+1] - numbers[i] > 15: 
      yield i+1 

def splitter(numbers): 
    # this function split the original list into sublists. 
    px = 0 
    for x in cut_indices(numbers): 
     yield numbers[px:x] 
     px = x 
    yield numbers[px:] 

def cluster(numbers): 
    # using the above result, to form a dict object. 
    cluster_ids = xrange(1,len(numbers)) 
    return dict(zip(cluster_ids, splitter(numbers))) 

print cluster(numbers) 

Powyższe kody dać mi

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

Answer 4

Oto stosunkowo proste rozwiązanie, które działa na listach lub generatorów. Leniwie daje to parę (group_number, element), więc musisz osobno grupować osobno, jeśli tego potrzebujesz. (A może wystarczy numer grupy.)

from itertools import tee 

def group(xs, gap=15): 
    # use `tee` to get two efficient iterators 
    xs1, xs2 = tee(xs) 

    # the first element is in group 0, also advance the second iterator 
    group = 0 
    yield (group, next(xs2)) 

    # after advancing xs2, this zip is pairs of consecutive elements 
    for x, y in zip(xs1, xs2): 
     # whenever the gap is too large, increment the group number 
     if y - x > gap: 
      group += 1 
     # and yield the second number in the pair 
     yield group, y