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