Schreiben Sie eine Funktion, die einen Satz von Ganzzahlen verwendet und jede Permutation des Satzes und den zwischen jedem Schritt durchgeführten Austausch druckt
Eingang
eine Menge von ganzen Zahlen, zum Beispiel (0, 1, 2)
Ausgabe
die Liste der Permutationen und Swaps im Format (Set) (Swap) (Set) ...
Testfall
Input:
(3, 1, 5)
Output:
(3, 1, 5)
(3, 1)
(1, 3, 5)
(3, 5)
(1, 5, 3)
(1, 3)
(3, 5, 1)
(3, 5)
(5, 3, 1)
(3, 1)
(5, 1, 3)
Regeln
- Sie können den Satz von Zahlen beliebig formatieren.
- Sie können die Swaps in beliebiger Reihenfolge durchführen
- Sie können Permutationen und Swaps wiederholen, um eine neue zu erhalten
- Ihr Code muss die Swaps nicht tatsächlich ausführen, die Ausgabe muss nur anzeigen, welcher Swap zwischen Ihrer letzten und Ihrer aktuellen Ausgabe durchgeführt wurde
- Ihr Code muss nur für Mengen mit 2 oder mehr Elementen funktionieren
- Der Satz, den Sie erhalten, enthält keine sich wiederholenden Elemente (z. B. (0, 1, 1, 2) ist ungültig).
Dies ist Code-Golf, also gewinnt der kürzeste Code!
code-golf
math
permutations
Billyoyo
quelle
quelle
(3, 1, 4)
oder so - ich habe es das erste Mal gelesen, als ich sehr verwirrt war, weil der erste Austausch0,1
die Elemente,0,1
aber auch die Indizes0,1
, aber dann den nächsten vertauschte Swap folgte nicht diesem Muster. Ich werde Sie auch auf die Sandbox verweisen, in der Sie Herausforderungen posten und Feedback erhalten können, bevor Sie sie auf der Hauptseite veröffentlichen.Antworten:
Mathematica, 102 Bytes
Beispiele
// Spalte für ein klareres Ergebnis
quelle
Java,
449426 BytesBrute-Force-Ansatz. Es werden so lange zufällige Swaps durchgeführt, bis alle möglichen Permutationen stattgefunden haben. Es wird ein Satz der Zeichenfolgendarstellung des Arrays verwendet, um zu überprüfen, wie viele verschiedene Zustände generiert wurden. Für n verschiedene ganze Zahlen gibt es n! = 1 * 2 * 3 * .. * n verschiedene Permutationen.
Aktualisieren
Ungolfed:
Verwendungszweck:
Wie Sie sehen, gibt es viel mehr Swaps als das erforderliche Minimum. Aber es scheint zu funktionieren :-D
Als Bonus funktioniert es auch mit Strings, dh
quelle
Set s=new HashSet();
. Ihr Code in der Methoden
kann eine einzelne Rückgabe sein :static int n(int x){return x==1?1:x*n(x-1);}
. Und Sie könnenString z
in Ihrer Methodeo
stattdessen durch ein generisches ersetzen :static<T>void o(T z){System.out.println(z);s.add(z);}
. Alles zusammen würde es auf 426 Bytes kommen .JavaScript (ES6), 186 Bytes
Hinweis: Ich bin mir nicht sicher, wie flexibel das Ausgabeformat ist. Möglicherweise kann ich dies für 171 Byte tun:
Funktioniert, indem der Steinhaus-Johnson-Trotter- Algorithmus für das Shuffle-Array von Indizes ausgeführt und in das Eingabearray zurückübersetzt wird. Ungolfed:
quelle
Ruby, 86 Bytes
quelle
Haskell - 135 Bytes
Ausgabe:
Ich verwende die Standardfunktion
permutations
, die nicht auf Swaps basiert, also nehme ich die Permutationen der Permutationen und finde eine, die zufällig eine Kette von Swaps ist.quelle