Finden von Schleifen zwischen Zahlen in einer Liste von Sets ⇐ Python

[Guest]

Ich habe meine Antwort als Antwort markiert, weil es diejenige ist, die das tut, was ich wollte, und jeder, der das Gleiche tun möchte, sollte dort beginnen. Aber ich würde gerne eine bessere Antwort sehen (Reihenfolge der Größenordnung für die Erzeugung aller Schleifen zum Beispiel D gezeigt) in Python und werde gerne eine bessere Antwort auswählen. Das ursprüngliche OP folgt.

Code: Select all

sets=[{1,2},{2,3},{1,3}]

Das Produkt (1,2,3) wird zweimal in itertools.product (*setzt) ​​ als Literale (1,2,3) generiert ) und (2,3,1) , weil es eine Schleife gibt. Wenn es keine Schleife gibt, gibt es keine Duplikation, obwohl es möglicherweise viel Gemeinsamkeit zwischen den Sätzen gibt. Set und dann zu B in einem anderen Satz, der A oder B in einem anderen Satz mit C hat, der sich mit einem Satz mit A. z. 1> 2--2> 3--3> 1 wobei '-' die Bewegung zwischen Sätzen und '>' angibt die Bewegung innerhalb des Satzes an. Die kleinste Schleife würde ein Zahlenpaar gemeinsam zwischen zwei Sätzen beinhalten, z. A> B-B> A . {bearbeiten: @ravenspoints Notation ist schön, ich schlage vor, {a} -b- {a} anstelle der oben genannten.} Loops in kanonischer Form sollte keinen Überbrückungswert mehr als einmal verwendet: Entweder dies stellt ein Fall, wo die Schleife auf sich selbst zurückverfolgt wurde (wie in einem Kursiv "I") oder es gibt kleinere Schleifen, die gemacht werden könnten (wie die äußeren und inneren Quadrate auf dem Arch de Triumph) (https://commons.wikimedia.org /wiki/file:paris_arc_de_triomphe.jpg).
Welche Art von Graphenstruktur könnte ich verwenden, um dies darzustellen? Zu welchem, aber das ist nicht richtig, da für [{1,2}, {1,3}, {1,4}] eine Verbindung zwischen allen Sätzen besteht- die gemeinsame 1- aber da ist keine Schleife. . < /p>
Dies wurde durch diese Frage zur Erzeugung einzigartiger Produkte motiviert. 17> 4 und längere Schleifen wie 13> 5--5> 11-11> 13 )
[{1, 13, 5}, {11, 13}, {17, 11, 4, 5}, {17, 4, 1}]
< /code>
kann wie in der DOCString von Core gezeigt generiert werden. Visualisieren Sie den "Pfad/die Schleife" sollen an Farbpunkte in einem Raster denken: Spalten enthalten Elemente der Sets und gleiche Elemente befinden sich in derselben Zeile. Eine Schleife ist ein Pfad, der an einem Punkt beginnt und am selben Punkt endet, indem sie vertikal oder horizontal von Punkt zu Punkt reisen und beide Bewegungsrichtungen enthalten müssen. Eine geeignete Permutation von Zeilen und Säulen würde ein Treppenpolygon zeigen.