[gelöst]Algorithmus ähnlich Permutation

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

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

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

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

[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

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

[HWK]

Vielleicht sind die Erläuterungen aber noch ganz hilfreich.
MfG
HWK