Das deutsche Python-Forum

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?

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

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

Oh ja, das sieht deutlich eleganter aus!

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

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

akis.kapo hat geschrieben: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

Hyperion hat geschrieben:
akis.kapo hat geschrieben: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...

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!

@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.

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".

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

Das deutsche Python-Forum

Lücken in Zahlensequenzen finden

Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden

Re: Lücken in Zahlensequenzen finden