Panjang siklus untuk pengocokan sempurna deck dengan berbagai ukuran

10

Tantangan

Dalam jumlah kode terpendek:

  1. Hitung panjang siklus permutasi dari shuffle sempurna pada setumpuk kartu dengan ukuran berapa pun n (di mana n ≥ 2 dan n genap).
  2. Keluarkan tabel semua panjang siklus selama 2 ≤ n ≤ 1000 ( n even).

Perhatikan bahwa ada dua cara dasar untuk mendefinisikan shuffle yang sempurna. Ada out-shuffle , yang menjaga kartu pertama di atas dan kartu terakhir di bawah, dan ada di-shuffle , yang memindahkan kartu pertama dan terakhir satu posisi ke arah tengah. Anda dapat memilih apakah Anda melakukan out-shuffle atau in-shuffle; Algoritma ini hampir identik di antara keduanya.

  • mengocok kartu 10-kartu: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5, 10].
  • in-shuffle dari 10 kartu deck: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10, 5].

Contoh grafis

Di sini, kita melihat bahwa out-shuffle pada dek 20-kartu memiliki panjang siklus 18 langkah. (Ini hanya sebagai ilustrasi; solusi Anda tidak diharuskan untuk menghasilkan siklus secara grafis.) Di sisi lain, dek 52 kartu klasik memiliki panjang siklus mengocok hanya 8 langkah (tidak diperlihatkan).

Siklus out-shuffle untuk deck 20-kartu

In -shuffle pada dek 20-kartu memiliki panjang siklus hanya 6 langkah.

Siklus in-shuffle untuk deck 20-kartu

Contoh output tabular

Program Anda harus menampilkan sesuatu yang mirip dengan ini, meskipun Anda dapat memilih format tabular apa saja yang paling Anda sukai. Ini untuk 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

Pertanyaan

  1. Apakah tampaknya ada hubungan antara input angka n dan jumlah siklusnya, ketika n adalah kekuatan 2?
  2. Bagaimana kalau n bukan kekuatan 2?
  3. Anehnya, kartu 1000-kartu memiliki hitungan siklus out-shuffle hanya 36, ​​sedangkan kartu 500-kartu memiliki jumlah siklus kartu-keluar-166 sebesar 166. Mengapa bisa demikian?
  4. Berapa jumlah terbesar yang dapat Anda temukan yang jumlah siklus c- nya jauh lebih kecil dari n , artinya rasio n / c dimaksimalkan?
Todd Lehman
sumber
1
Sangat terkait erat.
Martin Ender
Ya, itu lebih tentang menampilkan hasilnya. Pertanyaan ini adalah tentang membuat tabel untuk nilai n ; itu lebih bersifat matematika.
Todd Lehman
membingungkan saya di sana dengan siklus 6/8 di ditunjukkan untuk sementara waktu :) (saya pikir imlementation saya salah). akhirnya saya melihat gambar dan melihat itu adalah siklus 6, jadi saya mengeditnya. funny
bangga haskeller
@proud haskeller - ah ya, terima kasih!
Todd Lehman
1
Ini adalah urutan A002326 .
orlp

Jawaban:

6

Haskell, 47 46 44 (acak-acakan)

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

realisasi dasarnya adalah bahwa ini adalah urutan 2 dalam kelompok modulus multiplikasi n+1.

haskeller bangga
sumber
1
Anda dapat menghapus l=- ekspresi itu sendiri sudah cukup. Itu adalah program yang valid ketika dijalankan pada baris perintah interaktif.
orlp
5

Pyth, 16 byte

mfq1%^2T+3yd)500

Di-shuffle menggunakan A002326 .

orlp
sumber
2

Pyth, 22 byte

V500,JyhNl{.u.iFc2NJUJ

Cobalah online: Peragaan . Ganti 500 dengan angka yang lebih kecil, jika terlalu lambat.

Penjelasan:

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
sumber
1
Agak gila bahwa solusi pyth yang melakukan pekerjaan mengocok dan menghitung deck hanya setengah dari solusi haskell yang menggunakan formula mudah yang langsung memprediksi hasilnya
Falco
@ Falco saya tahu benar
bangga haskeller
1
@ Falco Saya benar-benar mencoba melakukan port pyth dari jawaban saya, tetapi saya tidak tahu bagaimana melakukannya. Jadi saya akhirnya bermain dengan pyth selama setengah jam
haskeller bangga
Senang Anda tidak mencoba <> <
Falco
2

Mathematica, 53 (di-acak-acakan)

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

atau, tidak ditempatkan secara antagonis

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

Keluaran:

   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

Setiap entri di kedua kolom secara horizontal terpusat di kolomnya, tapi saya tidak memiliki ruang fraksional &#8194;... di &#8202;sini untuk mereplikasi itu.

Pengamatan:

  • Out-shuffle adalah in-shuffle pada setumpuk dua kartu yang lebih kecil. (Perhatikan bahwa kartu pertama dan terakhir berada dalam posisi tetap di sepanjang demonstrasi out-shuffle.) Akibatnya, dua pilihan akan menghasilkan daftar output yang serupa - kolom kedua akan digeser oleh satu baris. Mengenai "kekuasaan dua" hint, dalam mengocok kekuasaan dari dua deck memiliki pola {2^n - 2, n}, {2^n, 2n}. (Mengocok pasangan 2^ndengan n.)
  • Perhatikan pada contoh in-shuffle bahwa jarak dari 2ujung terdekat dari geladak berlipat ganda pada setiap langkah. {2, 4, 8, 15 = -5, -10, -20}. Faktanya, ini berlaku untuk setiap kartu. Karena itu kita hanya perlu tahu kekuatan mana yang 2kongruen dengan 1mod di n+1mana njumlah kartu. (Perhatikan bahwa dalam contoh, kartu di kolom terakhir, kolom -1, digandakan ke kolom kedua dari belakang -2,, yang berarti 0kongruen dengan satu kartu lebih banyak daripada di geladak, dengan demikian "mod n+1".) Oleh karena itu, MultiplicativeOrder [] Fungsi adalah cara untuk pergi (dalam Mathematica).
  • Secara default, orang akan mencoba TableForm [] alih-alih Grid [], tetapi hasilnya serupa.
Menara Eric
sumber
Output contoh Anda tampaknya salah
haskeller bangga
@proudhaskeller: untuk in-shuffle atau out-shuffle? Keduanya diizinkan. (Dan seperti yang disebutkan, yang satu hanya satu baris pergeseran di kolom kanan yang lain.)
Eric Towers
Keduanya sepertinya tidak cocok. Lihat contoh output dalam pertanyaan. Mungkin output contoh Anda salah dan kode aktualnya benar dan contohnya sudah usang, saya tidak tahu, tetapi sepertinya tidak cocok.
haskeller bangga
proudhaskeller: Sepertinya saya salah ketik contoh keluaran saya di "8". Dan kacau di dalam dan luar- setidaknya sekali. Editing. Terima kasih sudah gigih. :-)
Eric Towers
0

C, 86 (atau 84)

Skor tidak termasuk spasi putih yang tidak perlu, termasuk untuk kejelasan.

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

Ini adalah in-shuffle, yang seperti ditunjukkan oleh orang lain, hanya shuffle keluar dengan kartu stasioner di kedua ujungnya dilepas.

Seperti yang ditunjukkan oleh orang lain, dalam in-shuffle, posisi setiap kartu berlipat ganda setiap kali, tetapi ini harus diambil modulo n+1. Saya suka memikirkan posisi kartu tambahan yang posisinya nol di sebelah kiri tabel (Anda dapat menganggap ini sebagai memegang kedua kartu stasioner dari out-shuffle juga). Jelas posisi kartu harus selalu positif, maka posisi nol selalu tetap kosong untuk case in-shuffle.

Kode diinisialisasi ike nilai n. Kemudian dikalikan dengan 2, mengambil mod hasil (n+1)dan memeriksa untuk melihat apakah itelah kembali ke nilai awal ( i-nadalah nol.) Peningkatan juntuk setiap iterasi, kecuali yang terakhir (maka kebutuhan diinisialisasi jke 1.)

Pada prinsipnya, ibisa dengan nilai apa pun dalam kisaran 1..n, asalkan perbandingan pada akhirnya diperiksa jika itu diinternalisasi ke nomor yang sama. Alasan memilih nadalah untuk memastikan program bekerja untuk kasus ini n==0. masalahnya adalah bahwa angka apa pun modulo (0+1)adalah nol, sehingga loop tidak pernah berakhir dalam kasus ini jika idiinisialisasi ke konstanta seperti 1.

Contoh-contoh pertanyaan mencakup kasus yang setara n==2untuk pengocokan keluar, sehingga ditafsirkan bahwa kasus ini diperlukan. Jika tidak, dua byte n,dapat disimpan dengan menginisialisasi ike 1, nilai yang sama dengan j.

Level River St
sumber