Ein Riffle-Shuffle ist eine Art von Shuffle, bei dem das Deck in zwei Partitionen aufgeteilt wird und die Partitionen dann wieder zusammengefügt werden, um ein neues gemischtes Deck zu erstellen.
Die Karten werden so zusammengefügt, dass die relative Reihenfolge der Karten in der Partition erhalten bleibt, in der sie Mitglied sind . Wenn die Karte zum Beispiel A vor Karte B im Deck und Karten A und B sind in der gleichen Partition, Karte A muss vor der Karte sein B im Endergebnis, auch wenn die Anzahl der Karten zwischen ihnen erhöht. Wenn sich A und B in unterschiedlichen Partitionen befinden, können sie im Endergebnis unabhängig von ihrer Startreihenfolge in beliebiger Reihenfolge sein.
Jedes Riffle-Shuffle kann dann als eine Permutation des ursprünglichen Kartenstapels angesehen werden. Zum Beispiel die Permutation
1,2,3 -> 1,3,2
ist ein Riffle Shuffle. Wenn Sie das Deck so teilen
1, 2 | 3
Wir sehen, dass jede Karte in 1,3,2
der Partition dieselbe relative Reihenfolge zu jeder anderen Karte in der Partition hat. 2
ist immer noch hinterher 1
.
Andererseits ist die folgende Permutation kein Riffle-Shuffle.
1,2,3 -> 3,2,1
Wir können dies sehen, weil für alle zwei (nicht-trivialen) Partitionen
1, 2 | 3
1 | 2, 3
Es gibt ein Paar Karten, deren relative Reihenfolge nicht eingehalten wird. In der ersten Partition 1
und 2
ändern Sie ihre Reihenfolge, während in der zweiten Partition 2
und 3
ändern Sie ihre Reihenfolge.
Wir sehen jedoch, dass 3, 2, 1
dies durch das Zusammenstellen von zwei Riffle-Shuffles erreicht werden kann.
1, 3, 2 + 2, 3, 1 = 3, 2, 1
In der Tat ist eine ziemlich einfache Tatsache, die bewiesen werden kann, dass jede Permutation gemacht werden kann, indem eine Anzahl von Riffle-Shuffle-Permutationen kombiniert wird.
Aufgabe
Ihre Aufgabe ist es, ein Programm oder eine Funktion zu erstellen , die eine Permutation (der Größe N ) als Eingabe verwendet und die kleinste Anzahl von Riffle-Shuffle-Permutationen (der Größe N ) ausgibt, die kombiniert werden können, um die Eingabepermutation zu bilden. Sie müssen die Riffle-Shuffles nicht selbst ausgeben, wie viele es gibt.
Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.
Sie können entweder 1 oder 0 für eine Identitätspermutation ausgeben.
Testfälle
1,3,2 -> 1
3,2,1 -> 2
3,1,2,4 -> 1
2,3,4,1 -> 1
4,3,2,1 -> 2
quelle
4,3,2,1
sein2
? Zuerst teilen wir uns in der Mitte und gewinnen,3,1,4,2
dann teilen wir uns wieder in der Mitte und verwenden die gleiche PermutationAntworten:
Python 3 , 255 Bytes
Überprüft alle möglichen Riffles bis zur Länge der Liste (maximale Anzahl erforderlich), daher ist es für größere Eingaben sehr langsam. Könnte wohl auch ganz schön golfen sein.
Probieren Sie es online!
quelle
Sauber ,
206... 185 BytesProbieren Sie es online!
Generiert alle möglichen Ergebnisse von Mischen-
n
Zeiten und prüft, ob die Liste ein Mitglied ist.Dies ist zwar eine schrecklich ineffiziente Methode zur Behebung des Problems, dieser Code ist jedoch besonders langsam da Listenverständnisse anstelle von Kompositionen verwendet werden, wodurch die Reduzierung elementarer Grafiken stark eingeschränkt führt zu einer spektakulären Präsentation von Clean's Garbage Collector.
Ungolfed:
Probieren Sie es online!
quelle