Défi

Dans la plus petite quantité de code:

1. Calculez la longueur du cycle de permutation d'un mélange parfait sur un jeu de cartes de n'importe quelle taille n (où n ≥ 2 et n est pair).
2. Afficher un tableau de toutes les longueurs de cycle pour 2 ≤ n ≤ 1000 ( n pair).

Notez qu'il existe deux méthodes de base pour définir un shuffle parfait. Il y a le shuffle out , qui garde la première carte en haut et la dernière carte en bas, et il y a le shuffle in , qui déplace les première et dernière cartes d'une position vers le centre. Vous pouvez choisir si vous faites un shuffle externe ou un shuffle interne; l'algorithme est presque identique entre les deux.

• mélange aléatoire du jeu de 10 cartes: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, dix].
• mélange de 10 cartes: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5].

Exemple graphique

Ici, nous voyons qu'un out-shuffle sur un jeu de 20 cartes a une durée de cycle de 18 étapes. (Ceci est uniquement à titre d'illustration; votre solution n'est pas requise pour produire des cycles graphiquement.) Le jeu de 52 cartes classique, d'autre part, a une durée de cycle de mélange aléatoire de seulement 8 étapes (non illustré).

Un in-shuffle sur un jeu de 20 cartes a une durée de cycle de seulement 6 étapes.

Exemple tabulaire de sortie

Votre programme devrait produire quelque chose de similaire à cela, bien que vous puissiez choisir le format tabulaire que vous préférez. C'est pour un shuffle out:

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

Des questions

1. Existe-t-il une connexion entre l'entrée numérique n et son nombre de cycles, lorsque n est une puissance de 2?
2. Et quand n n'est pas une puissance de 2?
3. Curieusement, un jeu de 1000 cartes a un nombre de cycles de shuffle de seulement 36, tandis qu'un jeu de 500 cartes a un nombre de cycles de shuffle de 166. Pourquoi est-ce possible?
4. Quel est le plus grand nombre que vous pouvez trouver dont le nombre de cycles c est largement inférieur à n , ce qui signifie que le rapport n / c est maximisé?

Haskell, 47 46 44 (en mode aléatoire)

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

la réalisation de base est que c'est de l'ordre de 2 dans le groupe multiplicatif de module n+1.

Pyth, 16 octets

mfq1%^2T+3yd)500

Mélange en utilisant A002326 .

Pyth, 22 octets

V500,JyhNl{.u.iFc2NJUJ

Essayez-le en ligne: démonstration . Remplacez 500 par un nombre plus petit, s'il est trop lent.

Explication:

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

Mathematica, 53 (en mélange)

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

ou, sans espacement antagoniste

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

Production:

   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

Chaque entrée dans les deux colonnes est centrée horizontalement dans leurs colonnes, mais je n'ai pas les espaces fractionnaires  ...  ici pour reproduire cela.

Observations:

• Out-shuffle est in-shuffle sur un jeu de deux cartes plus petites. (Notez que la première et la dernière carte sont en position fixe tout au long de la démonstration de mélange aléatoire.) Par conséquent, les deux choix mèneront à des listes de sortie similaires - la deuxième colonne sera décalée d'une ligne. En ce qui concerne les « puissances de deux » soupçon, en la lecture aléatoire de puissance de deux plate - formes a le motif {2^n - 2, n}, {2^n, 2n}. (Mélangez 2^navec n.)
• Observez dans l'exemple in-shuffle que la distance de 2l'extrémité la plus proche du jeu double à chaque étape. {2, 4, 8, 15 = -5, -10, -20}. En fait, cela est vrai pour chaque carte. Il suffit donc de savoir quelle puissance de 2est congru à 1mod n+1où se ntrouve le nombre de cartes. (Notez que dans l'exemple, les cartes de la dernière colonne, colonne -1, sont doublées à l'avant-dernière colonne, -2ce qui signifie que cela 0correspond à une carte de plus que dans le jeu, donc "mod n+1".) Par conséquent, le MultiplicativeOrder [] la fonction est le chemin à parcourir (dans Mathematica).
• Par défaut, on essaierait TableForm [] au lieu de Grid [], mais la sortie est similaire.

C, 86 (ou 84)

Le score exclut les espaces inutiles, inclus pour plus de clarté.

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++;
}

Il s'agit d'un shuffle d'entrée qui, comme l'ont souligné d'autres, n'est que le shuffle de sortie avec les cartes fixes aux deux extrémités retirées.

Comme indiqué par d'autres, dans le shuffle in-shuffle, la position de chaque carte double à chaque fois, mais cela doit être pris modulo n+1. J'aime à penser que la position de la carte supplémentaire est la position zéro à gauche de la table (vous pouvez aussi penser que cela tient les deux cartes stationnaires du mélange). Évidemment, la position de la carte doit toujours être positive, donc la position zéro reste toujours vide pour le cas de shuffle.

Le code s'initialise ià la valeur de n. Ensuite, il multiplie par 2, prend le mod de résultat (n+1)et vérifie si iest revenu à sa valeur initiale ( i-nest zéro.) Il incrémente jpour chaque itération, sauf la dernière (d'où la nécessité d'initialiser jà 1.)

En principe, ipourrait être avec n'importe quelle valeur dans la plage 1..n, tant que la comparaison à la fin vérifiait si elle était initialisée au même nombre. La raison du choix nétait de s'assurer que le programme fonctionne pour le cas n==0. le problème était que tout nombre modulo (0+1)est nul, donc la boucle ne s'est jamais terminée dans ce cas si elle a iété initialisée à une constante telle que 1.

Les exemples de questions incluent le cas équivalent n==2pour le shuffle out, il a donc été interprété que ce cas est requis. Si ce n'est pas le cas, deux octets n,pourraient être enregistrés en initialisant ià 1, la même valeur que j.