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

In Python, bei einer Liste von sortierten Integern, würde ich sie durch aufeinanderfolgende Werte gruppieren und Lücken von 1 tolerieren.

Zum Beispiel, bei einer Liste my_list :

  • Python-Gruppe eine Liste von Integer, mit den nächsten Werten
  • Zeigen Sie alle möglichen Gruppierungen einer Liste, nur die Menge der Unterlisten (Längen sind variabel)
  • Wie benutzt man Groupby, um Strings in Python-Pandas zu verketten?
  • Pandas - Groupby und neue DataFrame erstellen?
  • Wie bekomme ich die Anzahl der Gruppen in einem Groupby-Objekt in Pandas?
  • Gruppierung auf tems in einer liste in python
  •  In [66]: my_list Out[66]: [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] 

    Ich möchte die folgende Ausgabe:

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

    Nun, wenn ich keine Lücken von 1 tolerieren musste, konnte ich die hier beschriebene nette Lösung anwenden:

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

    Gibt es eine Möglichkeit, meine zusätzliche Anforderung in die obige Lösung zu integrieren? Wenn nicht, was ist der beste Weg, um das Problem anzugehen?

  • Pycharm-Umgebung anders als Kommandozeile
  • PyQt4 auf Mavericks mit Python 3
  • SSL Zertifikat Verifizierungsversagen in Python auf Mavericks
  • Python-Crashing beim Ausführen von zwei Befehlen (Segmentation Fault: 11)
  • Segfault 11 mit Pandas mit Python v2.7.6 RC1 auf Mac OS X 10.9
  • Installieren von lxml OSX Mavericks 10.9.2
  • 6 Solutions collect form web for “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_) .

    Python ist die beste Programmiersprache der Welt.