Seite 1 von 1
[gelöst]Algorithmus ähnlich Permutation
Verfasst: Samstag 4. Oktober 2008, 18:02
von DasIch
Ich habe eine unbestimmte Anzahl Listen mit einer unbestimmten Anzahl an Objekten(tuple), die Anzahl wird allerdings mit ziemlicher Sicherheit varieren.
Ich suche jetzt einen Algorithmus der mir alle Möglichkeiten ausgibt die Werte in den Listen in der Reihenfolge der Listen zu "verketten".
Das dass sicherlich sehr verwirrend klingt, mal ein kleines Beispiel:
Liste 0 : [(4,)]
Liste 1: [(1, 1), (2,)]
Liste 2: [(1,)]
Die Möglichkeiten wären jetzt:
[(4,), (1, 1), (1,)]
[(4,), (2,), (1,)]
Mir fällt irgendwie keine Möglichkeit ein mit der man dass Problem sinnvoll lösen könnte. Ich möchte keinen fertigen Code, einfach ein Tipp oder eine Idee die man umsetzen könnte würde mir schon reichen.
Verfasst: Samstag 4. Oktober 2008, 19:32
von Darii
Wenn ich dich richtig verstanden habe:
Code: Alles auswählen
def concatenate(*lists):
newlist = []
def concatenate_(lists, objects = None):
for obj in lists[0]:
if len(lists) == 1:
newlist.append([obj] + objects or [])
else:
concatenate_(lists[1:], objects = [obj] + (objects or []))
concatenate_(lists)
return newlist
Code: Alles auswählen
In [6]: Liste0=[(4,)]
In [7]: Liste1=[(1, 1), (2,),]
In [8]: Liste2=[(1,)]
In [9]: print concatenate(Liste0,Liste1,Liste2)
[[(1,), (1, 1), (4,)], [(1,), (2,), (4,)]]
PS: Gleich kommt hier sicherlich die schönere elegantere Lösung mit Generator und so
PPS/Edit: letzten Absatz hab ich doch glatt überlesen...
Verfasst: Samstag 4. Oktober 2008, 20:17
von Hyperion
Also ein Tipp wäre das ganze auf einen Baum zurückzuführen. Unterhalb des Wurzelknotens sind die Knoten aus der 1. Liste. Unter jedem Element der 1. Ebene stehen dann die der 2. Liste usw. Wie in der vorgeschlagenen Lösung kann man diesen Baum leicht rekursiv traversieren.
Verfasst: Sonntag 5. Oktober 2008, 03:25
von DasIch
Danke Darii, die Lösung ist kreativ aber ehrlich gesagt gefällt es mir nicht innerhalb von Funktionen nicht lokale Variablen(newlist) zu verändern. Ist in diesem Kontext eigentlich irrelevant aber es gefällt mir nicht so richtig, wobei ich da vielleicht eine Lösung gefunden hätte.
Über Hyperions Post hab ich eine weile nachdenken müssen(und nachschlagen was traversieren heisst
) aber eigentlich ist es ganz einfach und ich bin so zu einer Lösung gekommen.
Code: Alles auswählen
def foo(root):
if not root:
yield root
raise StopIteration
for element in root[0]:
for f in foo(root[1:]):
yield element, f
Der Namen sind nicht wirklich geschickt gewählt aber mir ist da jetzt spontan nichts passendes eingefallen. Ich muss nur noch an der Ausgabe feilen aber dass ist zu machen.
Verfasst: Sonntag 5. Oktober 2008, 09:13
von HWK
Wenn Du schon Python 2.6 installiert hast:
Code: Alles auswählen
IDLE 2.6
>>> a = [(4,)]
>>> b = [(1,1), (2,)]
>>> c = [(1,),]
>>> import itertools
>>> list(itertools.product(a, b, c))
[((4,), (1, 1), (1,)), ((4,), (2,), (1,))]
>>>
MfG
HWK
Verfasst: Sonntag 5. Oktober 2008, 22:20
von DasIch
Ah, dass ist nett. Ich werde aber bis für kleinere Experimente 2.6 noch nicht benutzen, solange sie zumindest bei meiner Distribution noch nicht über die Repos vefügbar.
Verfasst: Montag 6. Oktober 2008, 11:28
von HWK
Vielleicht sind die
Erläuterungen aber noch ganz hilfreich.
MfG
HWK