Tantangan
Dalam jumlah kode terpendek:
- Hitung panjang siklus permutasi dari shuffle sempurna pada setumpuk kartu dengan ukuran berapa pun n (di mana n ≥ 2 dan n genap).
- 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).
In -shuffle pada dek 20-kartu memiliki panjang siklus hanya 6 langkah.
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
- Apakah tampaknya ada hubungan antara input angka n dan jumlah siklusnya, ketika n adalah kekuatan 2?
- Bagaimana kalau n bukan kekuatan 2?
- 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?
- Berapa jumlah terbesar yang dapat Anda temukan yang jumlah siklus c- nya jauh lebih kecil dari n , artinya rasio n / c dimaksimalkan?
sumber
Jawaban:
Haskell,
474644 (acak-acakan)realisasi dasarnya adalah bahwa ini adalah urutan 2 dalam kelompok modulus multiplikasi
n+1
.sumber
l=
- ekspresi itu sendiri sudah cukup. Itu adalah program yang valid ketika dijalankan pada baris perintah interaktif.Pyth, 16 byte
Di-shuffle menggunakan A002326 .
sumber
Pyth, 22 byte
Cobalah online: Peragaan . Ganti 500 dengan angka yang lebih kecil, jika terlalu lambat.
Penjelasan:
sumber
Mathematica, 53 (di-acak-acakan)
atau, tidak ditempatkan secara antagonis
Keluaran:
Setiap entri di kedua kolom secara horizontal terpusat di kolomnya, tapi saya tidak memiliki ruang fraksional
 
... di 
sini untuk mereplikasi itu.Pengamatan:
{2^n - 2, n}
,{2^n, 2n}
. (Mengocok pasangan2^n
dengann
.)2
ujung 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 yang2
kongruen dengan1
mod din+1
manan
jumlah kartu. (Perhatikan bahwa dalam contoh, kartu di kolom terakhir, kolom-1
, digandakan ke kolom kedua dari belakang-2
,, yang berarti0
kongruen dengan satu kartu lebih banyak daripada di geladak, dengan demikian "modn+1
".) Oleh karena itu, MultiplicativeOrder [] Fungsi adalah cara untuk pergi (dalam Mathematica).sumber
C, 86 (atau 84)
Skor tidak termasuk spasi putih yang tidak perlu, termasuk untuk kejelasan.
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
i
ke nilain
. Kemudian dikalikan dengan 2, mengambil mod hasil(n+1)
dan memeriksa untuk melihat apakahi
telah kembali ke nilai awal (i-n
adalah nol.) Peningkatanj
untuk setiap iterasi, kecuali yang terakhir (maka kebutuhan diinisialisasij
ke 1.)Pada prinsipnya,
i
bisa dengan nilai apa pun dalam kisaran1..n
, asalkan perbandingan pada akhirnya diperiksa jika itu diinternalisasi ke nomor yang sama. Alasan memilihn
adalah untuk memastikan program bekerja untuk kasus inin==0
. masalahnya adalah bahwa angka apa pun modulo(0+1)
adalah nol, sehingga loop tidak pernah berakhir dalam kasus ini jikai
diinisialisasi ke konstanta seperti 1.Contoh-contoh pertanyaan mencakup kasus yang setara
n==2
untuk pengocokan keluar, sehingga ditafsirkan bahwa kasus ini diperlukan. Jika tidak, dua byten,
dapat disimpan dengan menginisialisasii
ke 1, nilai yang sama denganj
.sumber