[gelöst]Algorithmus ähnlich Permutation

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
DasIch
User
Beiträge: 2435
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Samstag 4. Oktober 2008, 18:02

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.
Zuletzt geändert von DasIch am Sonntag 5. Oktober 2008, 03:25, insgesamt 1-mal geändert.
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Samstag 4. Oktober 2008, 19:32

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...
Benutzeravatar
Hyperion
Moderator
Beiträge: 7472
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Samstag 4. Oktober 2008, 20:17

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
User
Beiträge: 2435
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 5. Oktober 2008, 03:25

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 :oops: ) 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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Sonntag 5. Oktober 2008, 09:13

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
User
Beiträge: 2435
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sonntag 5. Oktober 2008, 22:20

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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Montag 6. Oktober 2008, 11:28

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