Lücken in Zahlensequenzen finden

[Hyperion]

Hallo,

da ich gerade vor dem Problem stehe, in einer Sequenz von aufsteigenden Integer-Werten Lücken zu finden, habe ich überlegt, wie ich das in Python einfach umsetzen kann.

Die einfachste Art ist es wohl, die Lücken (=fehlende Zahlen) über Mengen zu finden:

Code: Alles auswählen

data = [1, 2, 4, 5]
set(range(1, data[-1] + 1)) - set(data)
>  set([3])

Die Anzahl lässt sich damit jedoch nicht feststellen.

Dafür fiel mir folgendes ein:

Code: Alles auswählen

def count_gaps(data):
    return sum(v > 1 for v in starmap(sub, (
        zip_longest(data, chain([0], data), fillvalue=data[-1]))))

count_gaps((1,2,4,6,7,10))
> 3

Wer hat noch andere Ideen?

[BlackJack]

Mit `itertools.tee()` funktioniert das auch für Iteratoren:

Code: Alles auswählen

def count_gaps(items):
    it_a, it_b = tee(items)
    next(it_b)
    return sum(b - a != 1 for a, b in izip(it_a, it_b))

[Hyperion]

Mit `itertools.tee()` funktioniert das auch für Iteratoren:

Oh ja, das sieht deutlich eleganter aus!

[akis.kapo]

Versteh ich nicht, wieso dein erster Codeabschnitt nicht auch zählen kann...

Code: Alles auswählen

>>> data = [1, 2, 4 ,5]
>>> newset = set(range(min(data), max(data) + 1)) - set(data)
>>> gaps = len(newset)
>>> gaps
1
>>> newset
set([3])

[pillmuncher]

Code: Alles auswählen

from itertools import tee, chain

flatten = chain.from_iterable

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def find_gaps(sorted_iterable):
    return ((i, j) for i, j in pairwise(sorted_iterable) if i + 1 != j)

def fill_gaps(sorted_iterable):
    return flatten(range(i + 1, j) for i, j in find_gaps(sorted_iterable))

def count_gaps(sorted_iterable):
    return len(list(find_gaps(sorted_iterable)))

if __name__ == '__main__':
    print(list(find_gaps([1, 2, 4, 5])))
    print(list(find_gaps([1, 2, 5, 6, 9])))
    print(list(fill_gaps([1, 2, 4, 5])))
    print(list(fill_gaps([1, 2, 5, 6, 9])))
    print(count_gaps([1, 2, 4, 5]))
    print(count_gaps([1, 2, 5, 6, 9]))

Ergebnis:

Code: Alles auswählen

[(2, 4)]
[(2, 5), (6, 9)]
[3]
[3, 4, 7, 8]
1
2

[Hyperion]

Versteh ich nicht, wieso dein erster Codeabschnitt nicht auch zählen kann...

Probiere es mal damit

Code: Alles auswählen

 data = [1, 2, 5, 6]

@pillmuncher: Nice

[akis.kapo]

Versteh ich nicht, wieso dein erster Codeabschnitt nicht auch zählen kann...

Probiere es mal damit

Code: Alles auswählen

 data = [1, 2, 5, 6]

@pillmuncher: Nice

Kannst du bitte erläutern, was genau du meinst?

Code: Alles auswählen

>>> data = [1,2,5,6]
>>> set(range(min(data),max(data)+1)) - set(data)
set([3, 4])
>>> len(set(range(min(data),max(data)+1)) - set(data))
2

Ist doch alles TOP!

Und pillmuncher zählt die gaps korrekt, aber er gibt dir nicht die Lücken zurück, sondern nur die lückenhaften Sequenzen, z.Bsp. "[(2, 4)]".
Was ist wenn dein data = [1, 99] ist? Dann bekämst du die selbe Menge zurück, statt [2, 3, 4, ..., 98].
Wolltest du das wirklich so haben? Vielleicht hab ich ja deine Anfo falsch verstanden...

[Hyperion]

Na, es ist doch nur *eine* Lücke! Die kann ja x fehlende Zahlen umfassen, aber es bleibt eine Lücke. Und das kann man mit Mengen nicht so einfach lösen

Und pillmunchers Rückgabe kann ich über ``len`` ja einfach auswerten!

[BlackJack]

@akis.kapo: Das korrekte Ergebnis ist aber nicht zwei sondern eins, denn es gibt zwischen 2 und 5 nur *eine* Lücke. Eben die wo die Zahlen 3 und 4 rein gehören um sie zu schliessen. Anzahl der Lücken meint nicht wie viele Zahlen fehlen sondern wie oft Zahlen in der Eingabe nicht direkt aufeinander folgen.

[akis.kapo]

Ok, sorry. Sprachproblem. Ich dachte Lücke = die fehlenden Elemente.

Irgendwas war schon komisch in diesem Thread... dacht ich mir schon "so einfach kann's nicht sein".

[BlackJack]

Hier noch mal mit Importen und einem Randfall:

Code: Alles auswählen

from itertools import izip, tee


def count_gaps(items):
    it_a, it_b = tee(items)
    try:
        next(it_b)
    except StopIteration:
        return 0
    else:
        return sum(b - a != 1 for a, b in izip(it_a, it_b))