Shuffle riffle adalah jenis shuffle di mana dek dibagi menjadi dua partisi dan partisi kemudian disambung kembali bersama untuk membuat deck dikocok baru.
Kartu-kartu disambungkan sedemikian rupa sehingga kartu mempertahankan urutan relatifnya di dalam partisi tempat mereka menjadi anggotanya . Misalnya, jika kartu A ada di depan kartu B di geladak dan kartu A dan B berada di partisi yang sama, kartu A harus di depan kartu B di hasil akhir, bahkan jika jumlah kartu di antara mereka telah meningkat. Jika A dan B berada di partisi yang berbeda, mereka dapat dalam urutan apa pun, terlepas dari urutan awal mereka, pada hasil akhir.
Setiap kocokan riffle kemudian dapat dilihat sebagai permutasi dari kartu asli. Misalnya permutasi
1,2,3 -> 1,3,2
adalah kocokan riffle. Jika Anda membagi deck seperti itu
1, 2 | 3
kita melihat bahwa setiap kartu di dalam 1,3,2
memiliki urutan relatif yang sama untuk setiap kartu lain di partisi itu. 2
masih setelah 1
.
Di sisi lain permutasi berikut ini bukan shuffle riffle.
1,2,3 -> 3,2,1
Kita dapat melihat ini karena untuk semua dua partisi (non-sepele)
1, 2 | 3
1 | 2, 3
ada sepasang kartu yang tidak mempertahankan pemesanan relatif mereka. Di partisi pertama 1
dan 2
ubah urutannya, sedangkan di partisi kedua 2
dan 3
ubah urutannya.
Namun kami melihat bahwa itu 3, 2, 1
dapat dibuat dengan membuat dua shuffle riffle,
1, 3, 2 + 2, 3, 1 = 3, 2, 1
Bahkan fakta yang cukup sederhana untuk dibuktikan adalah bahwa setiap permutasi dapat membuat saya menggabungkan beberapa jumlah permutasi acak riffle.
Tugas
Tugas Anda adalah membuat program atau fungsi yang menggunakan permutasi (ukuran N ) sebagai input dan menghasilkan jumlah permutasi shuffle riffle terkecil (ukuran N ) yang dapat digabungkan untuk membentuk permutasi input. Anda tidak perlu mengacak-acak shiffle sendiri berapa banyak.
Ini adalah kode-golf sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.
Anda dapat menghasilkan 1 atau 0 untuk permutasi identitas.
Uji Kasus
1,3,2 -> 1
3,2,1 -> 2
3,1,2,4 -> 1
2,3,4,1 -> 1
4,3,2,1 -> 2
sumber
4,3,2,1
seharusnya2
? Pertama kita berpisah di tengah dan mendapatkan3,1,4,2
dan kemudian kita berpisah di tengah lagi dan menggunakan permutasi yang samaJawaban:
Python 3 , 255 byte
Periksa semua kemungkinan riffle hingga panjang daftar (jumlah maksimum yang diperlukan), sehingga sangat lambat untuk input yang lebih besar. Mungkin juga bisa bermain golf sedikit.
Cobalah online!
sumber
Bersih ,
206... 185 byteCobalah online!
Menghasilkan setiap hasil yang mungkin dari
n
waktu pengocokan , dan memeriksa apakah daftar tersebut adalah anggota.Walaupun ini adalah cara yang sangat tidak efisien untuk menyelesaikan masalah, kode ini sangat lambat karena penggunaannya dari daftar pemahaman alih-alih komposisi, yang sangat membatasi pengurangan grafik dasar, dan menghasilkan karya yang spektakuler dari pengumpul sampah Clean.
Tidak Disatukan:
Cobalah online!
sumber