Identifizieren Sie Gruppen fortlaufender Zahlen in einer Liste

88

Ich möchte Gruppen fortlaufender Zahlen in einer Liste identifizieren, damit:

myfunc([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

Kehrt zurück:

[(2,5), (12,17), 20]

Und ich habe mich gefragt, was der beste Weg ist, dies zu tun (insbesondere, wenn in Python etwas eingebaut ist).

Bearbeiten: Hinweis Ich habe ursprünglich vergessen zu erwähnen, dass einzelne Nummern als einzelne Nummern und nicht als Bereiche zurückgegeben werden sollten.

Mikemaccana
quelle
3
Ist dieser Rückgabewert eine Zeichenfolge?
Mark Byers
Idealerweise würde ich etwas bevorzugen, das einen separaten Typ für Bereiche gegenüber eigenständigen Zahlen verwendet.
Mikemaccana

Antworten:

49

more_itertools.consecutive_groups wurde in Version 4.0 hinzugefügt.

Demo

import more_itertools as mit


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
[list(group) for group in mit.consecutive_groups(iterable)]
# [[2, 3, 4, 5], [12, 13, 14, 15, 16, 17], [20]]

Code

Mit diesem Tool erstellen wir eine Generatorfunktion, die Bereiche fortlaufender Zahlen findet.

def find_ranges(iterable):
    """Yield range of consecutive numbers."""
    for group in mit.consecutive_groups(iterable):
        group = list(group)
        if len(group) == 1:
            yield group[0]
        else:
            yield group[0], group[-1]


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
list(find_ranges(iterable))
# [(2, 5), (12, 17), 20]

Die Source - Implementierung emuliert eine klassische Rezeptur (wie durch @Nadia Alramli gezeigt).

Hinweis: more_itertoolsIst ein Paket eines Drittanbieters, das über installiert werden kann pip install more_itertools.

Pylang
quelle
118

EDIT 2: Um die neue OP-Anforderung zu beantworten

ranges = []
for key, group in groupby(enumerate(data), lambda (index, item): index - item):
    group = map(itemgetter(1), group)
    if len(group) > 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])

Ausgabe:

[xrange(2, 5), xrange(12, 17), 20]

Sie können xrange durch range oder eine andere benutzerdefinierte Klasse ersetzen.


Python-Dokumente haben ein sehr ordentliches Rezept dafür:

from operator import itemgetter
from itertools import groupby
data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    print map(itemgetter(1), g)

Ausgabe:

[2, 3, 4, 5]
[12, 13, 14, 15, 16, 17]

Wenn Sie genau die gleiche Ausgabe erhalten möchten, können Sie dies tun:

ranges = []
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    group = map(itemgetter(1), g)
    ranges.append((group[0], group[-1]))

Ausgabe:

[(2, 5), (12, 17)]

EDIT: Das Beispiel ist bereits in der Dokumentation erklärt, aber vielleicht sollte ich es mehr erklären:

Der Schlüssel zur Lösung liegt in der Differenzierung mit einem Bereich, sodass fortlaufende Nummern alle in derselben Gruppe angezeigt werden.

Wenn die Daten waren: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] Dann groupby(enumerate(data), lambda (i,x):i-x)entspricht dies den folgenden:

groupby(
    [(0, 2), (1, 3), (2, 4), (3, 5), (4, 12),
    (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)],
    lambda (i,x):i-x
)

Die Lambda-Funktion subtrahiert den Elementindex vom Elementwert. Also, wenn Sie das Lambda auf jeden Artikel anwenden. Sie erhalten die folgenden Schlüssel für groupby:

[-2, -2, -2, -2, -8, -8, -8, -8, -8, -8]

groupby gruppiert Elemente nach gleichem Schlüsselwert, sodass die ersten 4 Elemente zusammen gruppiert werden und so weiter.

Ich hoffe das macht es lesbarer.

python 3 Version kann für Anfänger hilfreich sein

Importieren Sie zuerst die erforderlichen Bibliotheken

from itertools import groupby
from operator import itemgetter

ranges =[]

for k,g in groupby(enumerate(data),lambda x:x[0]-x[1]):
    group = (map(itemgetter(1),g))
    group = list(map(int,group))
    ranges.append((group[0],group[-1]))
Nadia Alramli
quelle
4
funktioniert fast in py3k, außer es erfordert lambda x:x[0]-x[1].
SilentGhost
Könnten Sie bitte mehrstellige Variablennamen verwenden? Für jemanden, der nicht mit map () oder groupby () vertraut ist, sind die Bedeutungen von kg, i und x nicht klar.
Mikemaccana
1
Dies wurde aus den Python-Dokumentationen mit denselben Variablennamen kopiert. Ich habe jetzt die Namen geändert.
Nadia Alramli
1
Sie müssen die 2. Zahl in xrange / range erhöhen, da sie nicht inklusive ist. Mit anderen Worten [2,3,4,5] == xrange(2,6), nicht xrange(2,5). Es kann sinnvoll sein, einen neuen Datentyp für den inklusiven Bereich zu definieren.
IceArdor
10
Python 3 löst beim ersten Beispiel einen Syntaxfehler aus. Hier sind die ersten 2 Zeilen, die aktualisiert wurden, um an Python 3 zu arbeiten:for key, group in groupby(enumerate(data), lambda i: i[0] - i[1]): group = list(map(itemgetter(1), group))
derek73
16

Die "naive" Lösung, die ich zumindest etwas lesbar finde.

x = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 22, 25, 26, 28, 51, 52, 57]

def group(L):
    first = last = L[0]
    for n in L[1:]:
        if n - 1 == last: # Part of the group, bump the end
            last = n
        else: # Not part of the group, yield current group and start a new
            yield first, last
            first = last = n
    yield first, last # Yield the last group


>>>print list(group(x))
[(2, 5), (12, 17), (22, 22), (25, 26), (28, 28), (51, 52), (57, 57)]
Truppo
quelle
Ich mag diese Antwort sehr, weil sie knapp und doch lesbar ist. Zahlen, die außerhalb von Bereichen liegen, sollten jedoch als einzelne Ziffern und nicht als Tupel gedruckt werden (da ich die Ausgabe formatieren werde und unterschiedliche Formatierungsanforderungen für einzelne Zahlen im Vergleich zu Zahlenbereichen habe)
Mikemaccana
4
Die andere Antwort sah schön und intelligent aus, aber diese ist für mich verständlicher und erlaubte einem Anfänger wie mir, sie nach meinen Bedürfnissen zu erweitern.
Benny
Könnte ein Listenverständnis verwenden, um die Nicht-Bereichstupel als einzelne Ziffern zu drucken: print([i if i[0] != i[1] else i[0] for i in group(x)])
Nexus
14

Angenommen, Ihre Liste ist sortiert:

>>> from itertools import groupby
>>> def ranges(lst):
    pos = (j - i for i, j in enumerate(lst))
    t = 0
    for i, els in groupby(pos):
        l = len(list(els))
        el = lst[t]
        t += l
        yield range(el, el+l)


>>> lst = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
>>> list(ranges(lst))
[range(2, 6), range(12, 18)]
SilentGhost
quelle
2
[j - i for i, j in enumerate(lst)]ist schlau :-)
Jochen Ritzel
9

Hier sollte es funktionieren, ohne dass ein Import erforderlich ist:

def myfunc(lst):
    ret = []
    a = b = lst[0]                           # a and b are range's bounds

    for el in lst[1:]:
        if el == b+1: 
            b = el                           # range grows
        else:                                # range ended
            ret.append(a if a==b else (a,b)) # is a single or a range?
            a = b = el                       # let's start again with a single
    ret.append(a if a==b else (a,b))         # corner case for last single/range
    return ret
Andrea Ambu
quelle
6

Bitte beachten Sie, dass der verwendete Code groupbynicht wie in Python 3 angegeben funktioniert. Verwenden Sie diesen Code .

for k, g in groupby(enumerate(data), lambda x:x[0]-x[1]):
    group = list(map(itemgetter(1), g))
    ranges.append((group[0], group[-1]))
Mark Lawrence
quelle
3

Dies verwendet keine Standardfunktion - es iteriert nur über die Eingabe, aber es sollte funktionieren:

def myfunc(l):
    r = []
    p = q = None
    for x in l + [-1]:
        if x - 1 == q:
            q += 1
        else:
            if p:
               if q > p:
                   r.append('%s-%s' % (p, q))
               else:
                   r.append(str(p))
            p = q = x
    return '(%s)' % ', '.join(r)

Beachten Sie, dass die Eingabe nur positive Zahlen in aufsteigender Reihenfolge enthalten muss. Sie sollten die Eingabe validieren, aber dieser Code wird aus Gründen der Übersichtlichkeit weggelassen.

Mark Byers
quelle
1

Hier ist die Antwort, die ich mir ausgedacht habe. Ich schreibe den Code, damit andere ihn verstehen, also bin ich ziemlich ausführlich mit Variablennamen und Kommentaren.

Zuerst eine schnelle Hilfsfunktion:

def getpreviousitem(mylist,myitem):
    '''Given a list and an item, return previous item in list'''
    for position, item in enumerate(mylist):
        if item == myitem:
            # First item has no previous item
            if position == 0:
                return None
            # Return previous item    
            return mylist[position-1] 

Und dann der eigentliche Code:

def getranges(cpulist):
    '''Given a sorted list of numbers, return a list of ranges'''
    rangelist = []
    inrange = False
    for item in cpulist:
        previousitem = getpreviousitem(cpulist,item)
        if previousitem == item - 1:
            # We're in a range
            if inrange == True:
                # It's an existing range - change the end to the current item
                newrange[1] = item
            else:    
                # We've found a new range.
                newrange = [item-1,item]
            # Update to show we are now in a range    
            inrange = True    
        else:   
            # We were in a range but now it just ended
            if inrange == True:
                # Save the old range
                rangelist.append(newrange)
            # Update to show we're no longer in a range    
            inrange = False 
    # Add the final range found to our list
    if inrange == True:
        rangelist.append(newrange)
    return rangelist

Beispiellauf:

getranges([2, 3, 4, 5, 12, 13, 14, 15, 16, 17])

kehrt zurück:

[[2, 5], [12, 17]]
Mikemaccana
quelle
>>> getranges([2, 12, 13])Ausgänge : [[12, 13]]. War das beabsichtigt?
SilentGhost
Ja, ich muss einzelne Zahlen korrigieren (gemäß den meisten Antworten auf der Seite). Ich arbeite jetzt daran.
Mikemaccana
Eigentlich bevorzuge ich Nadias Antwort, groupby () scheint die Standardfunktion zu sein, die ich wollte.
Mikemaccana
1
import numpy as np

myarray = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
sequences = np.split(myarray, np.array(np.where(np.diff(myarray) > 1)[0]) + 1)
l = []
for s in sequences:
    if len(s) > 1:
        l.append((np.min(s), np.max(s)))
    else:
        l.append(s[0])
print(l)

Ausgabe:

[(2, 5), (12, 17), 20]

quelle
1

Die Verwendung von groupbyund countvon itertoolsgibt uns eine kurze Lösung. Die Idee ist, dass in zunehmender Reihenfolge die Differenz zwischen dem Index und dem Wert gleich bleibt.

Um den Index zu verfolgen, können wir eine itertools.count verwenden , die den Code sauberer macht als enumerate:

from itertools import groupby, count

def intervals(data):
    out = []
    counter = count()

    for key, group in groupby(data, key = lambda x: x-next(counter)):
        block = list(group)
        out.append([block[0], block[-1]])
    return out

Einige Beispielausgaben:

print(intervals([0, 1, 3, 4, 6]))
# [[0, 1], [3, 4], [6, 6]]

print(intervals([2, 3, 4, 5]))
# [[2, 5]]
Thierry Lathuille
quelle
0

Verwenden von numpy + -Verständnislisten:
Mit der numpy diff-Funktion können nachfolgende Eingabevektoreinträge identifiziert werden, deren Differenz nicht gleich eins ist. Der Anfang und das Ende des Eingabevektors müssen berücksichtigt werden.

import numpy as np
data = np.array([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

d = [i for i, df in enumerate(np.diff(data)) if df!= 1] 
d = np.hstack([-1, d, len(data)-1])  # add first and last elements 
d = np.vstack([d[:-1]+1, d[1:]]).T

print(data[d])

Ausgabe:

 [[ 2  5]   
  [12 17]   
  [20 20]]

Hinweis: Die Anforderung, dass einzelne Nummern unterschiedlich behandelt werden sollen (als einzelne zurückgegeben, nicht als Bereiche), wurde weggelassen. Dies kann durch weitere Nachbearbeitung der Ergebnisse erreicht werden. Normalerweise wird dies die Dinge komplexer machen, ohne einen Nutzen daraus zu ziehen.

Nir
quelle
0

Eine kurze Lösung, die ohne zusätzliche Importe funktioniert. Es akzeptiert alle iterierbaren Elemente, sortiert unsortierte Eingaben und entfernt doppelte Elemente:

def ranges(nums):
    nums = sorted(set(nums))
    gaps = [[s, e] for s, e in zip(nums, nums[1:]) if s+1 < e]
    edges = iter(nums[:1] + sum(gaps, []) + nums[-1:])
    return list(zip(edges, edges))

Beispiel:

>>> ranges([2, 3, 4, 7, 8, 9, 15])
[(2, 4), (7, 9), (15, 15)]

>>> ranges([-1, 0, 1, 2, 3, 12, 13, 15, 100])
[(-1, 3), (12, 13), (15, 15), (100, 100)]

>>> ranges(range(100))
[(0, 99)]

>>> ranges([0])
[(0, 0)]

>>> ranges([])
[]

Dies ist das Gleiche wie die Lösung von @ dansalmo, die ich erstaunlich fand, wenn auch etwas schwer zu lesen und anzuwenden (da sie nicht als Funktion angegeben ist).

Beachten Sie, dass es leicht geändert werden kann, um "traditionelle" offene Bereiche auszuspucken [start, end), indem z. B. die return-Anweisung geändert wird:

    return [(s, e+1) for s, e in zip(edges, edges)]

Ich habe diese Antwort von einer anderen Frage kopiert , die als Duplikat dieser Frage markiert war, um sie leichter auffindbar zu machen (nachdem ich gerade wieder nach diesem Thema gesucht hatte, zuerst nur die Frage hier gefunden hatte und mit den Antworten nicht zufrieden war gegeben).

Coldfix
quelle
0

Die Versionen von Mark Byers , Andrea Ambu , SilentGhost , Nadia Alramli und Truppo sind einfach und schnell. Die 'Truppo'-Version ermutigte mich, eine Version zu schreiben, die das gleiche flinke Verhalten beibehält, während andere Schrittgrößen als 1 behandelt werden (und als Singletons-Elemente aufgeführt werden, die mit einer bestimmten Schrittgröße nicht mehr als 1 Schritt erweitern). Es ist hier gegeben .

>>> list(ranges([1,2,3,4,3,2,1,3,5,7,11,1,2,3]))
[(1, 4, 1), (3, 1, -1), (3, 7, 2), 11, (1, 3, 1)]
smichr
quelle