Schleifen zwischen Zahlen in einer Liste von Mengen finden ⇐ Python

[Guest]

Angenommen eine Liste von Mengen wie:

Code: Select all

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

das Produkt (1,2,3) wird zweimal in itertools.product(*sets) generiert, da die Literale (1,2,3 ) und (2,3,1), weil es eine Schleife gibt. Wenn es keine Schleife gibt, gibt es keine Duplizierung, auch wenn es möglicherweise viele Gemeinsamkeiten zwischen Sätzen gibt.
Eine Schleife wird zu A in einem Satz gebildet, wenn Sie in demselben zu B reisen Menge und dann zu B in einer anderen Menge, die A hat, oder zu B in einer anderen Menge mit C, die mit einer Menge mit A verbunden ist. z.B. 1>2--2>3--3>1 wobei „--“ eine Bewegung zwischen Sätzen und „>“ eine Bewegung innerhalb des Satzes angibt. Die kleinste Schleife würde ein Zahlenpaar beinhalten, das zwei Mengen gemeinsam haben, z. B. a>b--b>a. {edit: Die Notation von @ravenspoint ist nett, ich schlage vor, {a}-b-{a} anstelle der oben genannten zu verwenden.} Schleifen in kanonischer Form sollten keinen Überbrückungswert haben: Entweder stellt dies einen Fall dar, in dem die Schleife, die auf sich selbst zurückgeführt wird (wie in einem kursiven „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 ... iomphe.jpg).
Welche Art von Diagrammstruktur könnte ich verwenden, um dies darzustellen? Jede Menge als Knoten und dann angeben, welche Mengen mit welchen verbunden sind. Dies ist jedoch nicht richtig, da für [{1,2},{1,3},{1,4}] eine Verbindung besteht zwischen allen Mengen – die gemeinsame 1 – aber Es gibt keine Schleife. Ich habe auch versucht, jeder Zahl in jedem Satz einen Buchstaben zuzuordnen, aber das scheint auch nicht richtig zu sein, da ich dann nicht weiß, wie ich Schleifen innerhalb unterscheiden soll Satz.
Dies wurde durch diese Frage zur Generierung einzigartiger Produkte motiviert.
Beispielsätze wie die folgenden (mit der trivialen Schleife 4>17- -17>4 und längere Schleifen wie 13>5--5>11--11>13)

Code: Select all

[{1, 13, 5}, {11, 13}, {17, 11, 4, 5}, {17, 4, 1}]

kann wie im Docstring von Core gezeigt generiert werden.
Alternative Visualisierungsanalogie
Eine andere Möglichkeit dazu Visualisieren Sie den „Pfad/die Schleife“, indem Sie sich Punkte in einem Raster vorstellen: Spalten enthalten Elemente der Mengen und gleiche Elemente befinden sich in derselben Zeile. Eine Schleife ist ein Pfad, der an einem Punkt beginnt und an demselben Punkt endet, indem er vertikal oder horizontal von Punkt zu Punkt verläuft und beide Bewegungsrichtungen umfassen muss. Eine geeignete Permutation von Zeilen und Spalten würde ein Treppenpolygon ergeben.