Herausforderung
In kürzester Menge Code:
- Berechnen Sie die Länge des Permutationszyklus eines perfekten Shuffle auf einem Kartenspiel beliebiger Größe n (wobei n ≥ 2 und n gerade ist).
- Geben Sie eine Tabelle aller Zykluslängen für 2 ≤ n ≤ 1000 ( n gerade) aus.
Beachten Sie, dass es zwei grundlegende Möglichkeiten gibt, ein perfektes Shuffle zu definieren. Es gibt das Out-Shuffle , bei dem die erste Karte oben und die letzte Karte unten bleiben, und das In-Shuffle , bei dem die erste und die letzte Karte um eine Position in Richtung Mitte verschoben werden. Sie können wählen, ob Sie ein Out-Shuffle oder ein In-Shuffle durchführen. Der Algorithmus ist zwischen beiden fast identisch.
- Out-Shuffle des 10-Karten-Decks: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, 10].
- In-Shuffle von 10-Karten-Deck: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5].
Grafisches Beispiel
Hier sehen wir, dass ein Out-Shuffle auf einem 20-Karten-Deck eine Zykluslänge von 18 Schritten hat. (Dies dient nur zur Veranschaulichung. Ihre Lösung muss keine Zyklen grafisch ausgeben.) Das klassische 52-Karten-Deck hat dagegen eine Out-Shuffle-Zykluslänge von nur 8 Schritten (nicht gezeigt).
Ein In-Shuffle auf einem 20-Karten-Deck hat eine Zykluslänge von nur 6 Schritten.
Tabellarisches Beispiel für die Ausgabe
Ihr Programm sollte etwas Ähnliches ausgeben, obwohl Sie ein beliebiges Tabellenformat auswählen können, das Ihnen am besten gefällt. Dies ist für ein Out-Shuffle:
2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10
36 12
38 36
40 12
...many lines omitted...
1000 36
Fragen
- Scheint es einen Zusammenhang zwischen dem Zahleneingang n und seiner Zykluszahl zu geben, wenn n eine Potenz von 2 ist?
- Wie wäre es, wenn n keine Potenz von 2 ist?
- Seltsamerweise hat ein 1000-Karten-Deck eine Out-Shuffle-Zykluszahl von nur 36, während ein 500-Karten-Deck eine Out-Shuffle-Zykluszahl von 166 hat. Warum könnte dies sein?
- Was ist die größte Zahl, die Sie finden können, deren Zykluszahl c erheblich kleiner als n ist , was bedeutet, dass das Verhältnis n / c maximiert ist?
quelle
Antworten:
Haskell,
474644 (gemischt)Die grundlegende Erkenntnis ist, dass dies die Größenordnung von 2 in der multiplikativen Gruppe des Moduls ist
n+1
.quelle
l=
- der Ausdruck selbst reicht aus. Dies ist ein gültiges Programm, wenn es über die interaktive Befehlszeile ausgeführt wird.Pyth, 16 Bytes
In-Shuffle mit A002326 .
quelle
Pyth, 22 Bytes
Probieren Sie es online aus: Demonstration . Ersetzen Sie 500 durch eine kleinere Zahl, wenn es zu langsam ist.
Erläuterung:
quelle
Mathematica, 53 (im Shuffle)
oder nicht antagonistisch beabstandet
Ausgabe:
Jeder Eintrag in beiden Spalten ist horizontal in ihren Spalten zentriert, aber ich habe nicht die gebrochenen Leerzeichen
 
... 
hier, um das zu replizieren.Beobachtungen:
{2^n - 2, n}
,{2^n, 2n}
. (Out-Shuffle-Paare2^n
mitn
.)2
vom nächsten Ende des Decks bei jedem Schritt verdoppelt.{2, 4, 8, 15 = -5, -10, -20}
. Tatsächlich gilt dies für jede Karte. Wir müssen daher nur wissen, welche Potenz von Mod2
kongruent ist, wo die Anzahl der Karten ist. (Beachten Sie, dass im Beispiel die Karten in der letzten Spalte, Spalte , auf die vorletzte Spalte verdoppelt werden , was bedeutet, dass eine Karte mehr kongruent ist als im Deck, also "mod ".) Daher der MultiplicativeOrder [] Funktion ist der richtige Weg (in Mathematica).1
n+1
n
-1
-2
0
n+1
quelle
C 86 (oder 84)
Die Punktzahl schließt unnötige Leerzeichen aus, die der Übersichtlichkeit halber enthalten sind.
Dies ist ein In-Shuffle, bei dem es sich, wie von anderen hervorgehoben, nur um das Out-Shuffle handelt, bei dem die stationären Karten an beiden Enden entfernt sind.
Wie von anderen betont, verdoppelt sich im In-Shuffle die Position jeder Karte jedes Mal, dies muss jedoch modulo genommen werden
n+1
. Ich stelle mir gerne vor, dass die zusätzliche Kartenposition die Position Null links vom Tisch ist (Sie können sich vorstellen, dass Sie auch beide stationären Karten aus dem Out-Shuffle halten). Offensichtlich muss die Position der Karte immer positiv sein, daher bleibt die Nullposition für den In-Shuffle-Fall immer leer.Der Code wird
i
auf den Wert von initialisiertn
. Dann multipliziert es mit 2, nimmt das Ergebnis mod(n+1)
und prüft, obi
es zu seinem Anfangswert zurückgekehrt ist (i-n
ist Null). Es erhöht sichj
für jede Iteration mit Ausnahme der letzten (daher mussj
auf 1 initialisiert werden ).Im Prinzip
i
könnte mit jedem Wert im Bereich sein1..n
, solange der Vergleich am Ende prüfte, ob er auf die gleiche Zahl initialisiert wurde. Der Grund für die Auswahln
war, sicherzustellen, dass das Programm für den Fall funktioniertn==0
. Das Problem war, dass jede Zahl Modulo(0+1)
Null ist, so dass die Schleife in diesem Fall nie beendet wurde, wenn siei
auf eine Konstante wie 1 initialisiert wurde.Die Fragenbeispiele enthalten den entsprechenden Fall
n==2
für das Out-Shuffle, daher wurde interpretiert, dass dieser Fall erforderlich ist. Wenn dies nicht dern,
Fall ist, können zwei Bytes durch Initialisiereni
auf 1 gespeichert werden , der gleiche Wert wiej
.quelle