Desafío

En la menor cantidad de código:

1. Calcule la duración del ciclo de permutación de una combinación perfecta en una baraja de cualquier tamaño n (donde n ≥ 2 yn es par).
2. Imprima una tabla de todas las longitudes de ciclo para 2 ≤ n ≤ 1000 ( n par).

Tenga en cuenta que hay dos formas básicas de definir una combinación aleatoria perfecta. Está la combinación aleatoria , que mantiene la primera carta en la parte superior y la última carta en la parte inferior, y está la combinación aleatoria , que mueve la primera y la última carta una posición hacia el centro. Puede elegir si está haciendo una combinación aleatoria o una aleatoria; El algoritmo es casi idéntico entre los dos.

• salida de baraja de 10 cartas: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, 10]
• en baraja de 10 cartas: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5]

Ejemplo gráfico

Aquí, vemos que una combinación aleatoria en un mazo de 20 cartas tiene una duración de ciclo de 18 pasos. (Esto es solo para ilustración; su solución no es necesaria para generar ciclos gráficamente). La clásica baraja de 52 cartas, por otro lado, tiene una duración de ciclo de reproducción aleatoria de solo 8 pasos (no se muestra).

Una combinación aleatoria en un mazo de 20 cartas tiene una duración de ciclo de solo 6 pasos.

Ejemplo tabular de salida

Su programa debería generar algo similar a esto, aunque puede elegir el formato tabular que más le guste. Esto es para una mezcla aleatoria:

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

Preguntas

1. ¿Parece haber alguna conexión entre el número de entrada ny su cuenta de ciclo, cuando n es una potencia de 2?
2. ¿Qué tal cuando n no es una potencia de 2?
3. Curiosamente, un mazo de 1000 cartas tiene un recuento de ciclo de shuffle de solo 36, mientras que un mazo de 500 cartas tiene un recuento de ciclo de shuffle de 166. ¿Por qué podría ser esto?
4. ¿Cuál es el número más grande que puede encontrar cuyo número de ciclos c es mucho más pequeño que n , lo que significa que la relación n / c está maximizada?

Haskell, 47 46 44 (en orden aleatorio)

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

la comprensión básica es que este es el orden de 2 en el grupo multiplicativo de módulo n+1.

Pyth, 16 bytes

mfq1%^2T+3yd)500

En barajado usando A002326 .

Pyth, 22 bytes

V500,JyhNl{.u.iFc2NJUJ

Pruébelo en línea: demostración . Reemplace 500 con un número más pequeño, si es demasiado lento.

Explicación:

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 (mezcla aleatoria)

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

o, no espaciados antagónicamente

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

Salida:

   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

Cada entrada en ambas columnas está centrada horizontalmente en sus columnas, pero no tengo los espacios fraccionarios  ...  aquí para replicar eso.

Observaciones:

• Out-shuffle es in-shuffle en una baraja dos cartas más pequeñas. (Tenga en cuenta que la primera y la última carta están en una posición fija durante toda la demostración). En consecuencia, las dos opciones darán lugar a listas de salida similares: la segunda columna se desplazará una fila. En cuanto a las "potencias de dos" pista, el en-barajada de poder de dos cubiertas tiene el patrón {2^n - 2, n}, {2^n, 2n}. (La combinación aleatoria se combina 2^ncon n).
• Observe en el ejemplo en combinación que la distancia 2desde el extremo más cercano de la baraja se duplica en cada paso. {2, 4, 8, 15 = -5, -10, -20}. De hecho, esto es cierto para cada tarjeta. Por lo tanto, solo necesitamos saber qué poder de 2es congruente con el 1mod, n+1dónde nestá el número de cartas. (Tenga en cuenta que en el ejemplo, las cartas en la última columna, columna -1, se duplican a la penúltima columna, -2lo que significa que 0es congruente con una carta más de la que está en el mazo, por lo tanto, "mod n+1".) Por lo tanto, el Orden Multiplicativa [] La función es el camino a seguir (en Mathematica).
• Por defecto, uno intentaría TableForm [] en lugar de Grid [], pero el resultado es similar.

C, 86 (u 84)

La puntuación excluye espacios en blanco innecesarios, incluidos para mayor claridad.

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

Esta es una combinación aleatoria, que según lo señalado por otros, es solo la combinación aleatoria con las tarjetas estacionarias en ambos extremos retiradas.

Como señalaron otros, en la combinación aleatoria, la posición de cada carta se duplica cada vez, pero esto debe tomarse en módulo n+1. Me gusta pensar que la posición de la carta extra es la posición cero a la izquierda de la mesa (puedes pensar en esto como si tuvieras ambas cartas estacionarias de la barajadura también). Obviamente, la posición de la carta siempre debe ser positiva, por lo tanto, la posición cero siempre permanece vacía para el caso de barajar.

El código se inicializa ial valor de n. Luego se multiplica por 2, toma el mod de resultados (n+1)y verifica si iha vuelto a su valor inicial ( i-nes cero). Se incrementa jpara cada iteración, excepto la última (de ahí la necesidad de inicializar ja 1.)

En principio, ipodría tener cualquier valor en el rango 1..n, siempre que la comparación al final verifique si se ha inicializado con el mismo número. La razón para elegir nfue asegurarse de que el programa funciona para el caso n==0. el problema era que cualquier módulo de número (0+1)es cero, por lo que el ciclo nunca terminaba en este caso si ise inicializaba a una constante como 1.

Los ejemplos de preguntas incluyen el caso equivalente n==2para la reproducción aleatoria, por lo que se interpretó que este caso es obligatorio. Si no es así, n,se pueden guardar dos bytes inicializando ia 1, el mismo valor que j.