Gibt es eine Abfolge von Swaps, die alle möglichen Permutationen generieren würden?

Question

Sie eine Liste von Zahlen gegeben sind 1, 2, ... ,n - gibt es eine Folge von n!-1swap Operationen, die alle n! Permutationen der Liste, wo erzeugen würde swap (i, j) Swaps Elemente in Zelle i und j? Was ist mit dem allgemeinen Fall, wenn die Eingabeliste nicht mit dem Anfang sortiert ist und/oder es Wiederholungen in der Liste gibt?

Kontext: Ich löse ein Problem, wo die "Punktzahl" eines Arrays leicht zu berechnen ist, wenn Sie bereits das Ergebnis kennen, wenn 2 Elemente getauscht werden und ich (alle C++ next_permutation()) alle möglichen Permutationen brute.

Answer 1

Sicher, und es war bekannt, Glockenläuten des 17. Jahrhunderts. Wie ist das für ein bisschen kombinatorische Geschichte?

Siehe the Steinhaus Johnson Trotter algorithm oder wenden Sie sich an Ihre lokale Rufgruppe.

---

habe ich ein wenig Forschung auf dem zweiten Teil Ihrer Frage, was ist, ob es möglich ist, diese Elemente mit wiederholt zu tun. Die Antwort ist, glaube ich, "ja, aber nicht so leicht". Darüber hinaus ist es nicht möglich, eine Liste mit wiederholten Elementen mit nur benachbarten Swaps zu permutieren, wie dies für die Menge {0, 0, 1, 1} leicht zu sehen ist. Dies ist jedoch nur mit einzelnen Swaps möglich.

Der grundlegende Ansatz besteht darin, den grundlegenden Algorithmus für die Änderung des Klingelns zu verwenden, jedoch auf Gruppen identischer Elemente statt auf einzelne Elemente. Für eine Gruppe von k identischen Elementen müssen Sie in der Lage sein, einen Algorithmus für Kombinationen der Liste 0 ^{n-k k} (wobei n die Gesamtgröße des Basissatzes ist). Es gibt eine Anzahl solcher Algorithmen, aber ich kann keine finden, die wirklich einfach sind; die einfachste ist (grob gesagt), der Gesamtgruppe eine Richtung zuzuordnen, und auch eine Richtung zu jedem 1 (ähnlich wie beim Shimon Even-Algorithmus). Wenn Sie die Gruppe nach links bewegen, fegt das Element ganz links vor und zurück; jedes Mal, wenn es die Richtung ändert, tritt das nächste mobile Element auf der rechten Seite ein; usw. Dies verschiebt schließlich die gesamte Gruppe von der rechten Seite der Liste zur linken Seite, woraufhin ihre Gesamtrichtung umgedreht wird und sie zu der ursprünglichen Konfiguration zurückkehrt, jetzt mit dem äußersten rechten Element, das die Sweeps führt.

Da die Anzahl der Richtungsumkehrungen auch in diesem Fall gleich sein könnte, kann der obige Algorithmus einen Permutationszyklus möglicherweise nicht verfolgen, aber ich glaube, dass es möglich ist, einen Zyklus mit einem ausgefeilteren Algorithmus zu erzeugen. In der Tat suchen Sie nach einem Hamilton-Zyklus in der Grafik, der durch mögliche einzelne Swaps aus jeder Permutation - eine Variante des Permutehedron - induziert wird. Aber während Hamilton-Zyklen existieren, sind sie nicht so einfach zu finden, da die Graphen sind ziemlich groß.