Identifier les groupes de nombres continus dans une liste

Question

Je tiens à identifier les groupes de nombres continus dans une liste, de sorte que:

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

retourne:

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

Et je me demandais quelle est la meilleure façon de le faire était (surtout si il ya quelque chose d'intégré en Python).

Edit: Notez l'origine, j'avais oublié de mentionner que des numéros individuels doivent être retournés comme des numéros individuels, pas des plages.

Answer 1

EDIT 2: pour répondre À la nouvelle exigence de l'OP

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

Sortie:

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

Vous pouvez remplacer xrange avec la gamme ou de toute autre classe personnalisée.

---

Python docs ont une très soigné recette pour ceci:

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)

Sortie:

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

Si vous souhaitez obtenir exactement le même résultat, vous pouvez faire ceci:

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

sortie:

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

---

EDIT: L'exemple est déjà expliqué dans la documentation, mais je devrais peut-être expliquer davantage:

La clé de la solution est la différenciation avec une gamme, de sorte que numéros consécutifs apparaissent tous dans le même groupe.

Si les données ont été: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] Ensuite, groupby(enumerate(data), lambda (i,x):i-x) est équivalente à la suivante:

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
)

La fonction lambda soustrait l'index de l'élément à partir de la valeur de l'élément. Ainsi, lorsque vous appliquez le lambda sur chaque élément. Vous obtiendrez les touches suivantes pour groupby:

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

groupby groupes d'éléments de même valeur de clé, de sorte que les 4 premiers éléments seront regroupés et ainsi de suite.

J'espère que cela le rend plus lisible.

Answer 2

Le "naïf" solution que je trouve un peu lisibles atleast.

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

Answer 3

En supposant que votre liste est triée:

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

Answer 4

Ici, c'est quelque chose qui devrait fonctionner, sans aucune importation nécessaires:

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

Answer 5

Ce n'est pas l'utilisation d'une fonction standard - il juste iiterates-dessus de l'entrée, mais il devrait fonctionner:

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)

Notez qu'il exige que l'entrée ne contient que des nombres positifs dans l'ordre croissant. Vous devez valider l'entrée, mais ce code est omis pour plus de clarté.