Seite 1 von 1

Gemeinsame Elemente einer beliebigen Anzahl Listen ermitteln

Verfasst: Montag 8. Januar 2007, 22:06
von Clython
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!

Verfasst: Montag 8. Januar 2007, 22:30
von rayo
Hi

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

Gruss

Verfasst: Montag 8. Januar 2007, 22:44
von birkenfeld
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.

Verfasst: Montag 8. Januar 2007, 23:12
von r2d2
> 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

Verfasst: Montag 8. Januar 2007, 23:24
von r2d2
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

Verfasst: Dienstag 9. Januar 2007, 00:54
von Clython
Danke r2d2!

Schon wieder ein paar neue Sachen gelernt :D !

Verfasst: Dienstag 9. Januar 2007, 09:24
von birkenfeld
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)

Verfasst: Dienstag 9. Januar 2007, 10:17
von Clython
Danke Birkenfeld. Du bestätigst, was ich mir gestern Nacht gedacht habe. War aber zu müde um es zu überprüfen.

Verfasst: Dienstag 9. Januar 2007, 12:44
von cracki
birkenfeld hat geschrieben:... map ... reduce ...
schoen funktional. sollte es oefters geben.

Verfasst: Dienstag 9. Januar 2007, 12:45
von sape
cracki hat geschrieben:
birkenfeld hat geschrieben:... map ... reduce ...
schoen funktional. sollte es oefters geben.
Dan schau dir mal die Sourcecodes von BlackJack an ;)

lg

Verfasst: Dienstag 9. Januar 2007, 15:56
von r2d2
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