Wyzwanie

W najkrótszym kodzie:

1. Oblicz długość cyklu permutacji idealnego tasowania na talii kart dowolnego rozmiaru n (gdzie n ≥ 2 i n jest parzyste).
2. Wyprowadzić tabelę wszystkich długości cyklu dla 2 ≤ n ≤ 1000 ( n parzystych).

Pamiętaj, że istnieją dwa podstawowe sposoby definiowania idealnego losowania. Istnieje tasowanie na zewnątrz , które utrzymuje pierwszą kartę na górze, a ostatnią na dole, i jest tasowanie , które przesuwa pierwszą i ostatnią kartę o jedną pozycję w kierunku środka. Możesz wybrać, czy wykonujesz przetasowanie, czy tasowanie; algorytm jest prawie identyczny między nimi.

• przetasowanie talii 10 kart: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, 10].
• tasowanie talii 10 kart: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5].

Przykład graficzny

Tutaj widzimy, że przetasowanie na talię 20 kart ma długość cyklu 18 kroków. (To tylko dla ilustracji; twoje rozwiązanie nie jest wymagane do graficznego generowania cykli). Z drugiej strony klasyczna talia 52 kart ma długość cyklu wymieszania wynoszącą tylko 8 kroków (nie pokazano).

Przetasowanie w talii 20 kart ma długość cyklu tylko 6 kroków.

Tabelaryczny przykład wyniku

Twój program powinien wypisać coś podobnego do tego, chociaż możesz wybrać dowolny format tabelaryczny, który najbardziej ci się podoba. To jest do przetasowania:

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

pytania

1. Czy wydaje się, że istnieje związek między wejściem liczbowym n a liczbą jego cykli, gdy n jest potęgą 2?
2. Co powiesz na to, kiedy n nie jest potęgą 2?
3. Co ciekawe, w przypadku talii 1000 kart liczba cykli wymieszania wynosi tylko 36, zaś w przypadku talii 500 kart liczba cykli wymieszania wynosi 166. Dlaczego tak może być?
4. Jaka jest największa liczba, jaką można znaleźć, której liczba cykli c jest znacznie mniejsza niż n , co oznacza, że ​​stosunek n / c jest zmaksymalizowany?

Haskell, 47 46 44 (w kolejności losowej)

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

podstawową realizacją jest to, że jest to rząd 2 w multiplikatywnej grupie modułu n+1.

Pyth, 16 bajtów

mfq1%^2T+3yd)500

Odtwarzanie losowe za pomocą A002326 .

Pyth, 22 bajty

V500,JyhNl{.u.iFc2NJUJ

Wypróbuj online: demonstracja . Wymień 500 na mniejszą liczbę, jeśli jest zbyt wolna.

Wyjaśnienie:

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 (in-shuffle)

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

lub, nie antagonistycznie rozmieszczone

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

Wynik:

   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

Każdy wpis w obu kolumnach jest wyśrodkowany w poziomie w kolumnach, ale nie mam ułamków ułamkowych  ...  tutaj, aby to odtworzyć.

Obserwacje:

• Przetasowywanie jest tasowaniem na talii o dwie karty mniejsze. (Zauważ, że pierwsza i ostatnia karta znajdują się w stałej pozycji podczas pokazu wymieszania.) W rezultacie dwie opcje doprowadzą do podobnych list wyników - druga kolumna zostanie przesunięta o jeden wiersz. Jeśli chodzi o „potęgami dwójki” nutą, w-shuffle mocą dwóch pokładów ma wzoru {2^n - 2, n}, {2^n, 2n}. (Out-shuffle pary 2^nz n.)
• Zauważ w przykładzie tasowania, że ​​odległość 2od najbliższego końca talii podwaja się na każdym kroku. {2, 4, 8, 15 = -5, -10, -20}. W rzeczywistości dotyczy to każdej karty. Dlatego musimy tylko wiedzieć, która moc 2odpowiada 1modowi, n+1gdzie njest liczba kart. (Zauważ, że w tym przykładzie karty w ostatniej kolumnie, kolumnie -1są podwojone do przedostatniej kolumny, -2co oznacza, że 0przystaje do jednej karty więcej niż w talii, a więc „mod n+1”.) Dlatego MultiplicativeOrder [] funkcja jest drogą do przejścia (w Mathematica).
• Domyślnie można wypróbować TableForm [] zamiast Grid [], ale dane wyjściowe są podobne.

C, 86 (lub 84)

Wynik wyklucza niepotrzebne białe znaki, uwzględnione dla zachowania przejrzystości.

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

Jest to tasowanie wewnętrzne, które, jak zauważyli inni, jest po prostu tasowaniem zewnętrznym z usuniętymi stacjonarnymi kartami na obu końcach.

Jak zauważyli inni, w tasowaniu pozycja każdej karty podwaja się za każdym razem, ale należy to wziąć modulo n+1. Lubię myśleć o tym, że dodatkowa pozycja karty to pozycja zero po lewej stronie stołu (możesz myśleć o tym jako o trzymaniu obu nieruchomych kart przed przetasowaniem). Oczywiście pozycja karty musi zawsze być dodatnia, dlatego pozycja zerowa zawsze pozostaje pusta dla przypadku tasowania.

Kod inicjuje isię do wartości n. Następnie mnoży przez 2, pobiera wynikowy mod (n+1)i sprawdza, czy ipowrócił do wartości początkowej ( i-nwynosi zero). Przyrostuje jdla każdej iteracji, z wyjątkiem ostatniej (stąd potrzeba inicjalizacji jna 1.)

Zasadniczo imoże mieć dowolną wartość z tego zakresu 1..n, o ile porównanie na końcu sprawdza się, czy zostało zainicjalizowane do tej samej liczby. Powodem pobrania nbyło upewnienie się, że program działa w przypadku n==0. problem polegał na tym, że dowolna liczba modulo (0+1)jest równa zero, więc pętla nigdy się nie kończy w tym przypadku, jeśli izostała zainicjowana na stałą, taką jak 1.

Przykłady pytań obejmują równoważny przypadek n==2tasowania wyjściowego, dlatego interpretowano, że ten przypadek jest wymagany. Jeśli tak nie jest, n,można zapisać dwa bajty, inicjując ina 1, taką samą wartość jak j.