Seite 1 von 1

Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 10:27
von pixewakb
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...

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 11:18
von __blackjack__
Da sollte es doch was passendes im `itertools`-Modul geben.

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 11:52
von nezzcarth
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?

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 11:53
von DasIch
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.

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 11:58
von pixewakb
DANKE!, das hilft mir sehr weiter!!!

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 14:26
von snafu
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?

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 14:50
von pixewakb
Das war ein Fehler meinerseits, gemeint waren alle möglichen Kombinationen zwischen den Werten. Sorry!

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Samstag 19. September 2020, 15:12
von __blackjack__
@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()

Re: Alle Kombinationen einer Liste mit Listen ermitteln

Verfasst: Mittwoch 23. September 2020, 08:51
von DeaD_EyE
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.