Come fare un `intervallo` inverso, cioè creare un intervallo compatto basato su un insieme di numeri?

Question

Python ha un metodo range, che consente di cose come:

>>> range(1, 6) 
[1, 2, 3, 4, 5] 

Quello che sto cercando è una specie di l'opposto: prendere una lista di numeri, e restituire l'inizio e la fine.

>>> magic([1, 2, 3, 4, 5]) 
[1, 5] # note: 5, not 6; this differs from `range()` 

Questo è abbastanza facile da fare per l'esempio precedente, ma è possibile consentire lacune o più intervalli così, tornando la gamma in un formato stringa di PCRE-like? Qualcosa di simile a questo:

>>> magic([1, 2, 4, 5]) 
['1-2', '4-5'] 
>>> magic([1, 2, 3, 4, 5]) 
['1-5'] 

Edit: sto cercando una soluzione Python, ma il benvenuto esempi di lavoro in altre lingue. Si tratta di capire un algoritmo elegante ed efficiente. Domanda bonus: esiste un linguaggio di programmazione che abbia un metodo integrato per questo?

Answer 1

Un bel trucco per semplificare il codice è quello di guardare la differenza di ogni elemento della lista ordinata e il suo indice:

a = [4, 2, 1, 5] 
a.sort() 
print [x - i for i, x in enumerate(a)] 

stampe

[1, 1, 2, 2] 

Ogni esecuzione dello stesso numero corrisponde ad una corsa di numeri consecutivi in ​​a. Ora possiamo usare itertools.groupby() per estrarre queste esecuzioni.Ecco il codice completo:

from itertools import groupby 

def sub(x): 
    return x[1] - x[0] 

a = [5, 3, 7, 4, 1, 2, 9, 10] 
ranges = [] 
for k, iterable in groupby(enumerate(sorted(a)), sub): 
    rng = list(iterable) 
    if len(rng) == 1: 
     s = str(rng[0][1]) 
    else: 
     s = "%s-%s" % (rng[0][1], rng[-1][1]) 
    ranges.append(s) 
print ranges 

stampa

['1-5', '7', '9-10'] 

Answer 2

Ordina i numeri, trova intervalli consecutivi (ricorda la compressione RLE?).

Qualcosa di simile a questo:

input = [5,7,9,8,6, 21,20, 3,2,1, 22,23, 50] 

output = [] 
first = last = None # first and last number of current consecutive range 
for item in sorted(input): 
    if first is None: 
    first = last = item # bootstrap 
    elif item == last + 1: # consecutive 
    last = item # extend the range 
    else: # not consecutive 
    output.append((first, last)) # pack up the range 
    first = last = item 
# the last range ended by iteration end 
output.append((first, last)) 

print output 

Risultato: [(1, 3), (5, 9), (20, 23), (50, 50)]. Calcola il resto :)

Answer 3

Questo è un tipo di elegante ma anche un po 'disgustoso, a seconda del punto di vista. :)

import itertools 

def rangestr(iterable): 
    end = start = iterable.next() 
    for end in iterable: 
     pass 
    return "%s" % start if start == end else "%s-%s" % (start, end) 

class Rememberer(object): 
    last = None 

class RangeFinder(object): 
    def __init__(self): 
     self.o = Rememberer() 

    def __call__(self, x): 
     if self.o.last is not None and x != self.o.last + 1: 
      self.o = Rememberer() 
     self.o.last = x 
     return self.o 

def magic(iterable): 
    return [rangestr(vals) for k, vals in 
      itertools.groupby(sorted(iterable), RangeFinder())] 


>>> magic([5,7,9,8,6, 21,20, 3,2,1, 22,23, 50]) 
['1-3', '5-9', '20-23', '50'] 

Spiegazione: utilizza itertools.groupby per raggruppare gli elementi ordinati insieme da una chiave, in cui la chiave è un oggetto Rememberer. La classe RangeFinder mantiene un oggetto Rememberer purché un gruppo consecutivo di elementi appartenga allo stesso blocco di intervallo. Una volta passato fuori da un determinato blocco, sostituisce lo Rememberer in modo che la chiave non sia paragonabile e groupby creerà un nuovo gruppo. Mentre groupby passa sopra l'elenco ordinato, passa gli elementi uno alla volta in rangestr, che costruisce la stringa ricordando il primo e l'ultimo elemento e ignorando tutto ciò che si trova in mezzo.

C'è qualche motivo pratico per utilizzare questo invece di 9000's answer? Probabilmente no; è fondamentalmente lo stesso algoritmo.

Answer 4

Dal 9000 mi ha battuto ad esso, mi limiterò a postare la seconda parte del codice, che consente di stampare intervalli di PCRE-come dalla precedente calcolato output più il tipo di controllo ha aggiunto:

for i in output: 
    if not isinstance(i, int) or i < 0: 
     raise Exception("Only positive ints accepted in pcre_ranges") 
result = [ str(x[0]) if x[0] == x[1] else '%s-%s' % (x[0], x[1]) for x in output ] 
print result 

uscita: ['1-3', '5-9', '20-23', '50']

Answer 5

ho pensato che ti avrebbe fatto piacere la mia soluzione clojure generalizzata.

(def r [1 2 3 9 10]) 

(defn successive? [a b] 
    (= a (dec b))) 

(defn break-on [pred s] 
    (reduce (fn [memo n] 
      (if (empty? memo) 
       [[n]] 
       (if (pred (last (last memo)) n) 
       (conj (vec (butlast memo)) 
         (conj (last memo) n)) 
       (conj memo [n])))) 
      [] 
      s)) 

(break-on successive? r) 

Answer 6

Proviamo i generatori!

# ignore duplicate values 
l = sorted(set([5,7,9,8,6, 21,20, 3,2,1, 22,23, 50])) 

# get the value differences 
d = (i2-i1 for i1,i2 in zip(l,l[1:])) 

# get the gap indices 
gaps = (i for i,e in enumerate(d) if e != 1) 

# get the range boundaries 
def get_ranges(gaps, l): 
    last_idx = -1 
    for i in gaps: 
    yield (last_idx+1, i) 
    last_idx = i 
    yield (last_idx+1,len(l)-1) 

# make a list of strings in the requested format (thanks Frg!) 
ranges = [ "%s-%s" % (l[i1],l[i2]) if i1!=i2 else str(l[i1]) \ 
    for i1,i2 in get_ranges(gaps, l) ] 

Questo è diventato piuttosto spaventoso, penso :)