Gruppieren Sie aufeinanderfolgende ganze Zahlen und tolerieren Sie Lücken von 1

Im Zweifelsfall können Sie immer Ihren eigenen Generator schreiben:

 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 

Demo:

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

Numpy ist ein sehr nützliches Werkzeug, und nicht sehr schwer zu lernen.

Dieses Problem ist in O(n) mit einer einzigen Codezeile lösbar (ohne Importe, Daten und Konvertierung in Liste – wenn Sie es wirklich brauchen):

 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) 

Noch wichtiger ist, dass der Code sehr schnell ist, wenn man große Listen verarbeiten muss, im Gegensatz zu einer rein-python-Lösung

Eine O (nlogn) -Lösung (vorausgesetzt, die Eingabeliste ist nicht sortiert) ist zunächst die Sortierung der Liste, die du gegeben hast, dann durch jeden Wert iterieren und eine neue Gruppe erstellen, wenn die Differenz zwischen dem aktuellen Wert und dem vorherigen Wert ist mindestens 3.

Demo

 >>> my_list = [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] >>> my_list.sort() # if we can't assume the list is sorted beforehand >>> groups = [[my_list[0]]] # initialize with the first value in the list >>> for i, val in enumerate(my_list[1:]): ... if val - groups[-1][-1] > 2: ... groups.append( [val] ) # create a new group ... else: ... groups[-1].append( val ) # append to the most recent group ... >>> groups [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Denken Sie daran, Groupby in sich, ist ziemlich lahm. Die Stärke von itertools.groupby ist der Schlüssel. Für dieses besondere Problem müssen Sie einen geeigneten Schlüssel mit Speicher erstellen (staatenloser Schlüssel wird hier nicht funktionieren).

Implementierung

 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] 

Objekt

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

Wie es funktioniert

Jedes Mal muss eine neue Unterliste erstellt werden ( curr - prev > threshold ), du schaltst ein Flag um. Es gibt verschiedene Möglichkeiten, eine Flagge zu wechseln

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

Wähle was dein Herz meint

So erzeugt dies einen begleitenden Schlüssel zusammen mit deiner Liste

 [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 

Nun, da itertools.groupby , Gruppen aufeinanderfolgende Elemente mit demselben Schlüssel, sind alle Elemente mit Tasten mit aufeinanderfolgenden 0 s oder 1 s zusammen gruppiert

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

Und dein letztes Ergebnis wäre

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

Hier ist, was ich kam mit. Es gibt ein bisschen ausführliche Initialisierung, aber es wird die Arbeit erledigt. =)

 output = [] prev = my_list[0] temp_list = [my_list[0]] for num in my_list[1:]: if num-2 > prev: output += [temp_list] temp_list = [num] else: temp_list.append(num) prev = num output.append(temp_list) print output # [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Ich benutze in der Regel zip wenn ich mit konsekutiven Elementen umgehen möchte, und Sie können islice Sie vermeiden möchten, das Listen-Slice zu bauen:

 from itertools import islice def group(lst, tol=1): """Group vals in sorted iterable lst, allow tol between consecutive vals.""" output = [[]] for current, next_ in zip(lst, islice(lst, 1, None)): output[-1].append(current) if next_ > current + tol + 1: output.append([]) output[-1].append(lst[-1]) return output 

Beachten Sie, dass in Python 2.x müssen Sie itertools.izip , um zu vermeiden, die Liste der 2-Tupel (current, next_) .