Zykluslängen für perfektes Mischen von Decks jeder Größe

10

Herausforderung

In kürzester Menge Code:

  1. Berechnen Sie die Länge des Permutationszyklus eines perfekten Shuffle auf einem Kartenspiel beliebiger Größe n (wobei n ≥ 2 und n gerade ist).
  2. 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).

Out-Shuffle-Zyklus für 20-Karten-Deck

Ein In-Shuffle auf einem 20-Karten-Deck hat eine Zykluslänge von nur 6 Schritten.

In-Shuffle-Zyklus für 20-Karten-Deck

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

  1. Scheint es einen Zusammenhang zwischen dem Zahleneingang n und seiner Zykluszahl zu geben, wenn n eine Potenz von 2 ist?
  2. Wie wäre es, wenn n keine Potenz von 2 ist?
  3. 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?
  4. 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?
Todd Lehman
quelle
1
Sehr eng verwandt.
Martin Ender
Ja, hier geht es jedoch mehr um die Anzeige der Ergebnisse. Bei dieser Frage geht es darum, eine Tabelle für einen beliebigen Wert von n zu generieren . Es ist eher mathematischer Natur.
Todd Lehman
verwirrte mich dort mit den 6/8 Zyklen in der für eine Weile demonstrierten :) (ich dachte meine Implementierung war falsch). Schließlich habe ich mir das Bild angesehen und festgestellt, dass es sich um einen 6-Zyklus handelt, also habe ich es bearbeitet. lustig
stolzer Haskeller
@proud haskeller - ah ja, danke!
Todd Lehman
1
Dies ist die Sequenz A002326 .
Orlp

Antworten:

6

Haskell, 47 46 44 (gemischt)

[[i|i<-[1..],mod(2^i)n<2]!!0|n<-[3,5..1001]]

Die grundlegende Erkenntnis ist, dass dies die Größenordnung von 2 in der multiplikativen Gruppe des Moduls ist n+1.

stolzer haskeller
quelle
1
Sie können das entfernen l=- der Ausdruck selbst reicht aus. Dies ist ein gültiges Programm, wenn es über die interaktive Befehlszeile ausgeführt wird.
Orlp
5

Pyth, 16 Bytes

mfq1%^2T+3yd)500

In-Shuffle mit A002326 .

orlp
quelle
2

Pyth, 22 Bytes

V500,JyhNl{.u.iFc2NJUJ

Probieren Sie es online aus: Demonstration . Ersetzen Sie 500 durch eine kleinere Zahl, wenn es zu langsam ist.

Erläuterung:

V500                     for N in [0, 1, ..., 499]:
      yhN                   (N + 1) * 2
     J                      assign to J
           .u      JUJ      apply the following expression J times
                            to N, starting with N = [0, 1, ..., J - 1],
                            and return all intermediate results:
                c2N            split N into 2 halfs
             .iF               and interleave them
         l{                 remove duplicates and give length
    ,                       make a pair and print
Jakube
quelle
1
Es ist irgendwie verrückt, dass eine Python-Lösung, die das eigentliche Mischen und Zählen der Decks erledigt, nur halb so lang ist wie die Haskell-Lösung, die eine einfache Formel verwendet, die das Ergebnis sofort vorhersagt
Falco
@ Falco Ich weiß richtig
stolzer Haskeller
1
@Falco Ich habe tatsächlich versucht, einen Python-Port meiner Antwort zu erstellen, konnte aber nicht herausfinden, wie das geht. Also habe ich gerade eine halbe Stunde mit
Python gespielt
Seien Sie froh, dass Sie <> <
Falco
2

Mathematica, 53 (im Shuffle)

Grid[{2#,MultiplicativeOrder[2,2#+1]}&/@Range[1,500]]

oder nicht antagonistisch beabstandet

Grid[{2 #, MultiplicativeOrder[2, 2 # + 1]} & /@ Range[1, 501]]

Ausgabe:

   2    2
   4    4
   6    3
   8    6
  10   10
  12   12
  14    4
  16    8
  18   18
  20    6
 (* digits, digits, bo bidgits, banana fana, ... *)
  498  166
  500  166
 (* skip a bit, brother ...  *)
  998   36
 1000   60

Jeder Eintrag in beiden Spalten ist horizontal in ihren Spalten zentriert, aber ich habe nicht die gebrochenen Leerzeichen &#8194;... &#8202;hier, um das zu replizieren.

Beobachtungen:

  • Out-Shuffle ist In-Shuffle auf einem Deck, das zwei Karten kleiner ist. (Beachten Sie, dass sich die erste und die letzte Karte während der Out-Shuffle-Demonstration in einer festen Position befinden.) Folglich führen die beiden Auswahlmöglichkeiten zu ähnlichen Ausgabelisten - die zweite Spalte wird um eine Zeile verschoben. In Bezug auf die „Zweierpotenz“ hint, hat die in-Shuffle der Macht von zwei Decks das Muster {2^n - 2, n}, {2^n, 2n}. (Out-Shuffle-Paare 2^nmit n.)
  • Beachten Sie im In-Shuffle-Beispiel, dass sich der Abstand 2vom 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 Mod 2kongruent 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).1n+1n-1-20n+1
  • Standardmäßig würde man TableForm [] anstelle von Grid [] versuchen, aber die Ausgabe ist ähnlich.
Eric Towers
quelle
Ihre Beispielausgabe scheint falsch
stolzer Haskeller
@proudhaskeller: für In-Shuffle oder Out-Shuffle? Beides ist erlaubt. (Und wie bereits erwähnt, ist die eine nur eine Zeilenverschiebung in der rechten Spalte der anderen.)
Eric Towers
Sie scheinen beide nicht zu passen. Schlagen Sie die Beispielausgabe in der Frage nach. Vielleicht ist Ihre Beispielausgabe falsch und der tatsächliche Code ist richtig und das Beispiel ist einfach veraltet, ich weiß es nicht, aber es scheint nicht zu passen.
stolzer Haskeller
stolzhaskeller: Ich habe anscheinend meine Beispielausgabe mit "8" getippt. Und mindestens einmal durcheinander. Bearbeitung. Danke, dass du hartnäckig bist. :-)
Eric Towers
0

C 86 (oder 84)

Die Punktzahl schließt unnötige Leerzeichen aus, die der Übersichtlichkeit halber enthalten sind.

i,j,n;
main(){
  for(;n<1002;printf("%d %d\n",n,j),n+=2)
    for(i=n,j=1;i=i*2%(n+1),i-n;)j++;
}

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 iauf den Wert von initialisiert n. Dann multipliziert es mit 2, nimmt das Ergebnis mod (n+1)und prüft, ob ies zu seinem Anfangswert zurückgekehrt ist ( i-nist Null). Es erhöht sich jfür jede Iteration mit Ausnahme der letzten (daher muss jauf 1 initialisiert werden ).

Im Prinzip ikönnte mit jedem Wert im Bereich sein 1..n, solange der Vergleich am Ende prüfte, ob er auf die gleiche Zahl initialisiert wurde. Der Grund für die Auswahl nwar, sicherzustellen, dass das Programm für den Fall funktioniert n==0. Das Problem war, dass jede Zahl Modulo (0+1)Null ist, so dass die Schleife in diesem Fall nie beendet wurde, wenn sie iauf eine Konstante wie 1 initialisiert wurde.

Die Fragenbeispiele enthalten den entsprechenden Fall n==2für das Out-Shuffle, daher wurde interpretiert, dass dieser Fall erforderlich ist. Wenn dies nicht der n,Fall ist, können zwei Bytes durch Initialisieren iauf 1 gespeichert werden , der gleiche Wert wie j.

Level River St.
quelle