Alle Kombinationen einer Liste mit Listen ermitteln

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
Benutzeravatar
pixewakb
User
Beiträge: 1409
Registriert: Sonntag 24. April 2011, 19:43

Ich habe folgende Datenstruktur

Code: Alles auswählen

liste = [[1], [2, 3], [4]]
und möchte dorthin:

Code: Alles auswählen

1 2 4
1 3 4
Tatsächlich wird meine Datenstruktur später etwa so aussehen:

Code: Alles auswählen

liste = [[1], [2, 3, 4], [5], [6, 7, 8], [9], [10, 11, 12, 13, 14], [15], [16]]
und entsprechend benötige ich alle "Pfade" durch diese Daten, also etwa 1, 2, 5, 6, 9, 10, 15, 16, dann 1, 2, 7, 9, 10, 15, 16 usw.

Hat jemand eine Idee, wie ich das elegant angehen könnte? Ich denke momentan an einen Graphen, in dem ich alle Wege bestimme, habe zum Thema bislang noch keinen Zugang und wäre hier für einen Hinweis auf einen verständlichen Einstieg dankbar.

BTW: Ich müsste das mit Bordmitteln lösen, d. h. keine Fremdbibliotheken...
Benutzeravatar
__blackjack__
User
Beiträge: 13006
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Da sollte es doch was passendes im `itertools`-Modul geben.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Nach deinem ersten Beispiel dachte ich, du suchst so etwas:

Code: Alles auswählen

>>> from itertools import product
>>> liste = [[1], [2, 3], [4]]
>>> list(product(*liste))
[(1, 2, 4), (1, 3, 4)]
>>> liste = [[1], [2, 3, 4], [5], [6, 7, 8], [9], [10, 11, 12, 13, 14], [15], [16]]
>>> list(product(*liste))
[(1, 2, 5, 6, 9, 10, 15, 16), (1, 2, 5, 6, 9, 11, 15, 16), (1, 2, 5, 6, 9, 12, 15, 16), (1, 2, 5, 6, 9, 13, 15, 16), (1, 2, 5, 6, 9, 14, 15, 16), (1, 2, 5, 7, 9, 10, 15, 16), (1, 2, 5, 7, 9, 11, 15, 16), (1, 2, 5, 7, 9, 12, 15, 16), (1, 2, 5, 7, 9, 13, 15, 16), (1, 2, 5, 7, 9, 14, 15, 16), (1, 2, 5, 8, 9, 10, 15, 16), (1, 2, 5, 8, 9, 11, 15, 16), (1, 2, 5, 8, 9, 12, 15, 16), (1, 2, 5, 8, 9, 13, 15, 16), (1, 2, 5, 8, 9, 14, 15, 16), (1, 3, 5, 6, 9, 10, 15, 16), (1, 3, 5, 6, 9, 11, 15, 16), (1, 3, 5, 6, 9, 12, 15, 16), (1, 3, 5, 6, 9, 13, 15, 16), (1, 3, 5, 6, 9, 14, 15, 16), (1, 3, 5, 7, 9, 10, 15, 16), (1, 3, 5, 7, 9, 11, 15, 16), (1, 3, 5, 7, 9, 12, 15, 16), (1, 3, 5, 7, 9, 13, 15, 16), (1, 3, 5, 7, 9, 14, 15, 16), (1, 3, 5, 8, 9, 10, 15, 16), (1, 3, 5, 8, 9, 11, 15, 16), (1, 3, 5, 8, 9, 12, 15, 16), (1, 3, 5, 8, 9, 13, 15, 16), (1, 3, 5, 8, 9, 14, 15, 16), (1, 4, 5, 6, 9, 10, 15, 16), (1, 4, 5, 6, 9, 11, 15, 16), (1, 4, 5, 6, 9, 12, 15, 16), (1, 4, 5, 6, 9, 13, 15, 16), (1, 4, 5, 6, 9, 14, 15, 16), (1, 4, 5, 7, 9, 10, 15, 16), (1, 4, 5, 7, 9, 11, 15, 16), (1, 4, 5, 7, 9, 12, 15, 16), (1, 4, 5, 7, 9, 13, 15, 16), (1, 4, 5, 7, 9, 14, 15, 16), (1, 4, 5, 8, 9, 10, 15, 16), (1, 4, 5, 8, 9, 11, 15, 16), (1, 4, 5, 8, 9, 12, 15, 16), (1, 4, 5, 8, 9, 13, 15, 16), (1, 4, 5, 8, 9, 14, 15, 16)]
Wie unterscheidet sich das von dem Gewünschten?
Zuletzt geändert von nezzcarth am Samstag 19. September 2020, 11:54, insgesamt 1-mal geändert.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Ich denke momentan an einen Graphen[...]
Algorithmen in dem Bereich häufig ziemlich ineffizient und kompliziert. Überall finden sich Probleme die NP-Hard sind. Graphen sind so ein bisschen wie reguläre Ausdrücke, wenn du damit versuchst ein Problem zu lösen hast du plötzlich zwei. Wenn du also nicht sowieso schon ein Graphproblem hast (hast du nicht), hält man davon besser Abstand.
Benutzeravatar
snafu
User
Beiträge: 6732
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

nezzcarth hat geschrieben: Samstag 19. September 2020, 11:52 Wie unterscheidet sich das von dem Gewünschten?
Dein Ansatz unterscheidet sich bereits beim zweiten Tupel, sofern man nach der o.g. "Musterlösung" geht. ;)

Mit ist allerdings das Muster bzw die genaue Anforderung noch nicht klar geworden. Es ist beim zweiten Tupel ja 1,2,7,... gewünscht. Welchen Hintergrund hat das?
Benutzeravatar
pixewakb
User
Beiträge: 1409
Registriert: Sonntag 24. April 2011, 19:43

Das war ein Fehler meinerseits, gemeint waren alle möglichen Kombinationen zwischen den Werten. Sorry!
Benutzeravatar
__blackjack__
User
Beiträge: 13006
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@DasIch: Ob das ein Graphenproblem ist, hängt davon ab ob man es als solches formuliert. Und man kann echt viel als Graphenproblem formulieren. Und hat dann schon eine Menge Standardalgorithmen auf die man zurückgreifen kann. Effizienz ist dann natürlich oft eine Frage die sich stellt.

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import chain

import networkx as nx
from more_itertools import pairwise

SOURCE, SINK = "source", "sink"


def main():
    # data = [[1], [2, 3], [4]]
    data = [
        [1],
        [2, 3, 4],
        [5],
        [6, 7, 8],
        [9],
        [10, 11, 12, 13, 14],
        [15],
        [16],
    ]

    graph = nx.DiGraph()
    for sources, targets in pairwise(chain([[SOURCE]], data, [[SINK]])):
        graph.add_edges_from(
            (source, target) for target in targets for source in sources
        )

    for path in nx.shortest_simple_paths(graph, SOURCE, SINK):
        print(path[1:-1])


if __name__ == "__main__":
    main()
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
DeaD_EyE
User
Beiträge: 1012
Registriert: Sonntag 19. September 2010, 13:45
Wohnort: Hagen
Kontaktdaten:

Ich finde es ziemlich cool, dass es z.B. so etwas gibt: https://networkx.github.io/documentatio ... aths.astar
Passt zwar nicht zur Aufgabe, aber ein Blick kann ja nicht schaden.
sourceserver.info - sourceserver.info/wiki/ - ausgestorbener Support für HL2-Server
Antworten