Listenlücken

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Listenlücken

Beitragvon uphill » Donnerstag 14. Dezember 2006, 17:26

Hi,
ich hab hier eine liste, und wollte wissen wie ich am schnellsten eine Lücke finde. zB:

Code: Alles auswählen

li = [1,2,3,5,12]


in diesem Fall die 4


Code: Alles auswählen

li = [1,2,3,4,5,12]


und in diesem die 6...

danke

uphill
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 14. Dezember 2006, 17:42

Wenn du nur die erste Lücke haben willst, kannst du diese hübsch obskure LC nehmen:

Code: Alles auswählen

[first for first, second in enumerate(li) if first+1 != second][0] + 1


Eine anständige, mehrzeilige Lösung zu finden ist mir im Moment zu anstrengend 8)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Beitragvon BlackJack » Donnerstag 14. Dezember 2006, 18:07

Etwas speicherschonender:

Code: Alles auswählen

(first for first, second in enumerate(li) if first+1 != second).next() + 1


:-)

Beide Varianten fallen leider auf die Nase wenn keine Lücke vorhanden ist. :-(
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Donnerstag 14. Dezember 2006, 19:32

Code: Alles auswählen

def find_spaces(iterable):
    last = None
    for item in iterable:
        if last is not None and last + 1 != item:
            yield last
        last = item
TUFKAB – the user formerly known as blackbird
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » Donnerstag 14. Dezember 2006, 21:38

Wie ineffizient ;-). Das läuft ja in O(N), man kann es aber auch in O(log N) machen:

Code: Alles auswählen

def find_gap(list):
    first = list[0]
    step = len(list)
    pos = step/2
    while True:
        step /= 2
        if pos >= len(list):
            pos = len(list)-1
        if list[pos] != first + pos:
            if step == 0:
                return pos
            pos -= step
        else:
            pos += step
        if step == 0:
            return False
(Nicht zu ernst nehmen)
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Beitragvon uphill » Donnerstag 14. Dezember 2006, 22:41

@linduas das geht nicht mit 0

Code: Alles auswählen

[first for first, second in enumerate(li) if first+1 != second][0] + 1



Code: Alles auswählen

In [12]: li = [0,1,2,12,23,43,255]

In [13]: [first for first, second in enumerate(li) if first+1 != second][0] + 1
Out[13]: 1
[/quote]
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 14. Dezember 2006, 22:51

uphill hat geschrieben:@linduas das geht nicht mit 0

Bitte Augen etwas nach links drehen, und dort meinen Nick korrekt ablesen. Dankeschön.

Ansonsten: hast recht. Das liegt daran, dass enumerate mit 0 zu zählen anfängt und nicht mit dem ersten Element der übergebenen Liste. Dazu müsste man eine alternative Emumerate-Funktion implementieren. Dummerweise geht bei mir die Shell grad nicht, sonst könnte ich dir schnell einen Quelltext posten. Andererseits ist es auch egal, weil blackbird schon eine universellere Möglichkeit gepostet hat.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Donnerstag 14. Dezember 2006, 23:10

>> Dazu müsste man eine alternative Emumerate-Funktion implementieren
Wie wäre es mit `whiletake` @ `count(1)` @ `Liste` in einer LC?

EDIT: Ich meinte natürlich `takewhile` ^^ Naja, bin aber ehe nicht der Fan von `takewhile` ;) Brauchte ich bis her nicht.
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Donnerstag 14. Dezember 2006, 23:20

Blödsinn -> über `izip(count(1), Liste)` iterieren

:roll: @Sape!!
BlackJack

Beitragvon BlackJack » Donnerstag 14. Dezember 2006, 23:42

Jau, um diesen Gedanken mal zuende zu führen:

Code: Alles auswählen

from itertools import count, groupby, imap, izip
from operator import itemgetter


def search_first_gap(iterable):
    dummy, before_gap = groupby(izip(iterable, count()),
                                key=lambda (a, b): a - b).next()
    return max(imap(itemgetter(0), before_gap)) + 1


def main():
    data = [0, 1, 2, 3, 4, 5, 12]
    print search_first_gap(data)
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Freitag 15. Dezember 2006, 01:20

Wow, sieht wie immer wider sehr nach FP aus :D Puh, das werde ich mal morgen genauer studieren. Sieht auf jeden fall sehr interessant und (für mich) Kompliziert aus.

lg
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Beitragvon uphill » Freitag 15. Dezember 2006, 17:12

@BlackJakck:
cooler ansatz nur leider nich python 2.3 kompatibel

greez
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Beitragvon uphill » Freitag 15. Dezember 2006, 17:27

danke auf jeden fall für die vielen Antworten aber leider funzt der yield ansatz von BlackJack komischer weise auch nicht. Versteh allerdings nicht so genau warum.


greez.
uphill
User
Beiträge: 22
Registriert: Sonntag 10. Dezember 2006, 20:17

Beitragvon uphill » Freitag 15. Dezember 2006, 17:38

Code: Alles auswählen

def find_spaces(iterable):
   last = None
   for item in iterable:
      if last is not None and last + 1 != item:
         yield last+1
      last = item


das geht, und das werd ich verwenden und nochmal thx@all
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon sape » Freitag 15. Dezember 2006, 21:06

Jao, nun hab ich BlackJacks Beispiel verstanden. Wieder was dazugelernt! :D

lg

Wer ist online?

Mitglieder in diesem Forum: dark_universe