Gemeinsame Elemente einer beliebigen Anzahl Listen ermitteln

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.
Antworten
Clython
User
Beiträge: 151
Registriert: Samstag 21. August 2004, 13:58
Wohnort: Schweiz, BE-2500

Montag 8. Januar 2007, 22:06

Hallo mein Code, den ich aus meiner Klasse rausgenommen habe sieht so aus:

Code: Alles auswählen

    def _schnittmenge(self, definition):
        length = 0
        lead = None
        result = []
        for x in definition:
            if len(x) > length:
                lead = x # ermittel die längste Liste als Grundlage des Algorithmus
        definition.remove(lead) 
        print lead
        for x in self.defs[lead].values(): #Hole Lead-Liste aus Dictionary
            for iden in x:
                state = True
                while state:
                    for y in definition:
                        if iden in y:
                            pass
                        else:
                            state = False
                            break
                        result.append(x)
Der Code sieht nicht nur stümperhaft aus (und ist es auch), er funktioniert anscheinend auch nicht. Gibt es für diese Aufgabe ein Built-In oder habt ihr sogar eine bessere Funktion/Methode dazu? Oder vielleicht hat mir jemand ein Stichwort, dass mich auf einen schlaueren Pfad lotst?

Danke Leute!
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Montag 8. Januar 2007, 22:30

Hi

Für Mengenoperationen (Schnittmenge) würde ich dir den Datentyp set empfehlen (ab Py2.5) sonst einfach das Modul Sets anschauen.

Gruss
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Montag 8. Januar 2007, 22:44

rayo hat geschrieben:Hi

Für Mengenoperationen (Schnittmenge) würde ich dir den Datentyp set empfehlen (ab Py2.5) sonst einfach das Modul Sets anschauen.
Das `set`-Builtin gibt es tatsächlich sogar schon ab Python 2.4.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Montag 8. Januar 2007, 23:12

> Oder vielleicht hat mir jemand ein Stichwort, dass mich auf einen schlaueren Pfad lotst?

die kürzeste - nicht die längste liste - soll als grundlage dienen. die schnittmange kann nur so lang wie die kürzeste liste sein.

r2d2
äh, nimm diese schlange von meinem hals.
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Montag 8. Januar 2007, 23:24

mal aus die husche:

Code: Alles auswählen

mylist = [[1], [1,2], [1,2,3]]
def schnittmenge(definition):
    liste = min(definition) # holt die kürzeste ohne sie zu löschen
    result = []
    for i in definition:
        for i2 in i:
            if i2 in liste and i2 not in result:
                result.append(i2)
    return result

print schnittmenge(mylist)
läuft und ist - glaube ich - sonst selbsterlärend.

r2d2
äh, nimm diese schlange von meinem hals.
Clython
User
Beiträge: 151
Registriert: Samstag 21. August 2004, 13:58
Wohnort: Schweiz, BE-2500

Dienstag 9. Januar 2007, 00:54

Danke r2d2!

Schon wieder ein paar neue Sachen gelernt :D !
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Dienstag 9. Januar 2007, 09:24

r2d2 hat geschrieben:mal aus die husche:

Code: Alles auswählen

mylist = [[1], [1,2], [1,2,3]]
def schnittmenge(definition):
    liste = min(definition) # holt die kürzeste ohne sie zu löschen
    result = []
    for i in definition:
        for i2 in i:
            if i2 in liste and i2 not in result:
                result.append(i2)
    return result

print schnittmenge(mylist)
läuft und ist - glaube ich - sonst selbsterlärend.
Und falsch.

min(definition) holt nicht die kürzeste Liste, Gegenbeispiel [[3], [2, 1]].
Richtig gehts mit min(definition, key=len).

Außerdem ist der Algorithmus falsch. Wenn du den Schnitt von
[1,2,3], [1,2,3] und [4,5,6,7-] bildest muss [] herauskommen. Bei dir ist es [1,2,3].

Eine korrekte Lösung mit sets lautet etwa:

Code: Alles auswählen

def schnittmenge(definition):
    if not definition: return []
    return list(reduce(set.intersection, map(set, definition)))
Wenn man reduce() ausschreibt, ergibt das

Code: Alles auswählen

def schnittmenge(definition):
    if not definition:
        return []
    iterator = iter(definition)
    result = set(iterator.next()) # erstes Element
    for liste in iterator: # alle übrigen Elemente
        result &= set(liste)
    return list(result)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Clython
User
Beiträge: 151
Registriert: Samstag 21. August 2004, 13:58
Wohnort: Schweiz, BE-2500

Dienstag 9. Januar 2007, 10:17

Danke Birkenfeld. Du bestätigst, was ich mir gestern Nacht gedacht habe. War aber zu müde um es zu überprüfen.
cracki
User
Beiträge: 72
Registriert: Montag 25. Dezember 2006, 05:01

Dienstag 9. Januar 2007, 12:44

birkenfeld hat geschrieben:... map ... reduce ...
schoen funktional. sollte es oefters geben.
...meh...
sape
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Dienstag 9. Januar 2007, 12:45

cracki hat geschrieben:
birkenfeld hat geschrieben:... map ... reduce ...
schoen funktional. sollte es oefters geben.
Dan schau dir mal die Sourcecodes von BlackJack an ;)

lg
r2d2
User
Beiträge: 43
Registriert: Donnerstag 2. März 2006, 23:05
Wohnort: Bielefeld

Dienstag 9. Januar 2007, 15:56

ich hab heute nacht mist geschrieben - es war schon spät.

ich hatte zwar den richtigen gedanken, aber das gehirn hat um diese späte stunde wohl ausgesetzt.

hier noch mal ein versuch ohne set

Code: Alles auswählen

mylist = [[1,3,2,4], [1,2], [1,2,3], [1,2,4,7,8]]
def schnittmenge(definition):
    liste = definition[0] # holt beliebige liste 0, 1, 2 oder 3
    result = []
    for i in liste:
        for i2 in definition:
            if i not in i2:
                if i in result: result.remove(i)
                break
            if i in i2 and i in result: continue
            if i not in result: result.append(i)
    return result

print schnittmenge(mylist)
r2d2
äh, nimm diese schlange von meinem hals.
Antworten