Gemeinsame Elemente einer beliebigen Anzahl Listen ermitteln

[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!

[rayo]

Hi

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

Gruss

[birkenfeld]

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.

[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

[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

[Clython]

Danke r2d2!

Schon wieder ein paar neue Sachen gelernt !

[birkenfeld]

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)

[Clython]

Danke Birkenfeld. Du bestätigst, was ich mir gestern Nacht gedacht habe. War aber zu müde um es zu überprüfen.

[cracki]

... map ... reduce ...

schoen funktional. sollte es oefters geben.

[sape]

... map ... reduce ...

schoen funktional. sollte es oefters geben.

Dan schau dir mal die Sourcecodes von BlackJack an

lg

[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