Desafio

Na menor quantidade de código:

1. Calcule a duração do ciclo de permutação de um baralhamento perfeito em um baralho de cartas de qualquer tamanho n (onde n ≥ 2 e n são pares).
2. Emita uma tabela de todos os comprimentos de ciclo para 2 ≤ n ≤ 1000 ( n pares).

Observe que existem duas maneiras básicas de definir um shuffle perfeito. Existe a saída aleatória , que mantém a primeira carta no topo e a última carta na parte inferior, e há a entrada aleatória , que move a primeira e a última cartas uma posição em direção ao centro. Você pode escolher se está fazendo um embaralhamento ou embaralhamento; o algoritmo é quase idêntico entre os dois.

• embaralhamento do baralho de 10 cartas: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, 10]
• baralhamento do baralho de 10 cartas: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5]

Exemplo gráfico

Aqui, vemos que uma saída aleatória em um baralho de 20 cartas tem uma duração de ciclo de 18 etapas. (Isso é apenas ilustrativo; sua solução não é necessária para gerar ciclos graficamente.) O baralho clássico de 52 cartas, por outro lado, possui um ciclo de saída aleatória de apenas 8 etapas (não mostrado).

Um embaralhamento em um baralho de 20 cartas tem uma duração de ciclo de apenas 6 etapas.

Exemplo tabular de saída

Seu programa deve gerar algo semelhante a isso, embora você possa escolher qualquer formato tabular que mais lhe agrade. Isto é para uma saída aleatória:

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

Questões

1. Parece haver alguma conexão entre a entrada numérica n e sua contagem de ciclos, quando n é uma potência de 2?
2. Que tal quando n não é uma potência de 2?
3. Curiosamente, um baralho de 1000 cartas tem uma contagem de ciclo de shuffle de apenas 36, enquanto um baralho de 500 cartas tem uma contagem de ciclo de shuffle de 166. Por que isso pode acontecer?
4. Qual é o maior número que você pode encontrar cuja contagem de ciclos c é muito menor que n , o que significa que a razão n / c é maximizada?

Haskell, 47 46 44 (em ordem aleatória)

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

a percepção básica é que essa é a ordem de 2 no grupo multiplicativo de módulo n+1.

Pitão, 16 bytes

mfq1%^2T+3yd)500

Em ordem aleatória usando A002326 .

Pitão, 22 bytes

V500,JyhNl{.u.iFc2NJUJ

Experimente online: Demonstração . Substitua 500 por um número menor, se estiver muito lento.

Explicação:

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 (em ordem aleatória)

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

ou, não antagonisticamente espaçado

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

Resultado:

   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 nas duas colunas é centralizada horizontalmente nas colunas, mas eu não tenho os espaços fracionários  ...  aqui para replicar isso.

Observações:

• Baralhar para fora é baralhar para dentro de um baralho duas cartas menores. (Observe que a primeira e a última placa estão em posição fixa durante toda a demonstração de reprodução aleatória.) Conseqüentemente, as duas opções levarão a listas de saída semelhantes - a segunda coluna será deslocada em uma linha. Em relação às "potências de dois" dica, o in-arrastar de poder de dois decks tem o padrão {2^n - 2, n}, {2^n, 2n}. (Pares aleatórios 2^ncom n.)
• Observe no exemplo de reprodução aleatória que a distância da 2extremidade mais próxima do baralho dobra a cada passo. {2, 4, 8, 15 = -5, -10, -20}. De fato, isso é verdade para todos os cartões. Portanto, precisamos apenas saber qual potência 2é congruente para 1modificar n+1onde nestá o número de cartões. (Observe que no exemplo, as cartas da última coluna, coluna -1, são dobradas para a penúltima coluna, -2o que significa que 0é congruente com mais uma carta do que no baralho, portanto, "mod n+1".) Portanto, o MultiplicativeOrder [] função é o caminho a percorrer (no Mathematica).
• Por padrão, alguém tentaria TableForm [] em vez de Grid [], mas a saída é semelhante.

C, 86 (ou 84)

A pontuação exclui espaços em branco desnecessários, incluídos para maior clareza.

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

Este é um embaralhamento, que, como indicado por outros, é apenas o embaralhamento com as cartas estacionárias nas duas extremidades removidas.

Conforme apontado por outros, no embaralhamento, a posição de cada carta dobra a cada vez, mas isso deve ser tomado como módulo n+1. Eu gosto de pensar que a posição extra da carta está na posição zero à esquerda da mesa (você pode pensar nisso como segurando as duas cartas estacionárias da saída aleatória também). Obviamente, a posição do cartão deve sempre ser positiva; portanto, a posição zero sempre permanece vazia para o caso de embaralhamento.

O código é inicializado icom o valor de n. Em seguida, ele multiplica por 2, pega o resultado mod (n+1)e verifica se iretornou ao seu valor inicial ( i-né zero). Ele aumenta jpara cada iteração, exceto a última (daí a necessidade de inicializar jpara 1.)

Em princípio, ipode estar com qualquer valor no intervalo 1..n, desde que a comparação no final verifique se foi inicializada com o mesmo número. O motivo da escolha nfoi garantir que o programa funcionasse para o caso n==0. o problema era que qualquer módulo numérico (0+1)é zero; portanto, o loop nunca terminava nesse caso se ifosse inicializado para uma constante como 1.

Os exemplos de perguntas incluem o caso equivalente n==2para o shuffle de saída, portanto, foi interpretado que esse caso é necessário. Caso contrário, dois bytes n,podem ser salvos, inicializando ipara 1, o mesmo valor que j.