Kemarin saya menanyakan pertanyaan ini tentang riffle shuffles. Tampaknya pertanyaan kemarin agak terlalu sulit sehingga pertanyaan ini adalah tugas yang terkait tetapi jauh lebih mudah.
Hari ini Anda diminta untuk menentukan apakah permutasi benar-benar mengacak. Definisi kami tentang riffle shuffle diadaptasi dari pertanyaan terakhir kami:
Bagian pertama dari shuffle adalah pembagian. Di partisi membagi tumpukan kartu menjadi dua. Dua subbagian harus kontinu, saling eksklusif dan lengkap. Di dunia nyata ingin membuat partisi Anda sedekat mungkin, namun dalam tantangan ini ini bukan pertimbangan, semua partisi termasuk yang merosot (satu partisi kosong) memiliki pertimbangan yang sama.
Setelah dipartisi, kartu-kartu disambungkan sedemikian rupa sehingga kartu-kartu mempertahankan urutan relatifnya di dalam partisi tempat mereka menjadi anggota . 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.
Tugas
Diberi permutasi melalui metode yang masuk akal, tentukan apakah itu merupakan shuffle riffle yang valid. Anda harus menampilkan dua nilai konstanta berbeda satu untuk "Ya, ini adalah riffle shuffle" dan satu untuk "Tidak, ini bukan riffle shuffle".
Ini adalah kode-golf sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte lebih baik.
Uji Kasus
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
sumber
0
untuk falsy tetapi bilangan bulat apa pun[1, +∞)
untuk kebenaran?[3,1,4,2,5]
.[2,3,6,1,4,5]
.[0, ..., n-1]
alih-alih[1, ..., n]
sebagai input?Jawaban:
JavaScript (ES6), 47 byte
Mengambil input sebagai array bilangan bulat. Mengembalikan boolean.
Uji kasus
Tampilkan cuplikan kode
Bagaimana?
Array input A adalah shuffle riffle yang valid jika terdiri dari paling banyak dua urutan interlaced berbeda dari integer berurutan.
Aturan tantangan menentukan bahwa kita diberi permutasi dari [1 ... N] . Jadi kita tidak perlu memeriksa tambahan bahwa penyatuan urutan dari urutan ini benar-benar menghasilkan kisaran seperti itu.
Kami menggunakan penghitung x yang diinisialisasi ke A [0] dan penghitung y awalnya tidak terdefinisi.
Untuk setiap entri z dalam A , dimulai dengan entri ke-2:
sumber
Haskell , 41 byte
Cobalah online!
Cek apakah daftar yang disatukan dengan dirinya sendiri berisi angka-angka
0..n-1
sebagai urutan.sumber
Haskell , 43 byte
s
mengambil daftar bilangan bulat seperti pada contoh OP dan mengembalikan aBool
.Cobalah online!
Bagaimana itu bekerja
x
darip
pada gilirannya dan cek jika dapat menjadi elemen pertama dari partisi kedua shuffle. Kemudianor
kembaliTrue
jika ada cekTrue
.filter
)p
ke dalam elemen yang lebih kecil dan lebih besar dari (atau sama dengan)x
, menyatukan, dan memeriksa apakah daftar yang dihasilkan adalah[1..length p]
, yaitu elemen-elemen dalam urutan.[1..length p]
dilakukan dengan melihat apakah hasilnya benar-benar lebih kecil dari daftar yang tak terbatas[1..] == [1,2,3,etc.]
, yang memberikan hasil yang sama untuk permutasi apa pun.sumber
Jelly ,
136 byteCobalah online!
Versi alternatif, tantangan tanggal kiriman, 5 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python 2 , 39 byte
Cobalah online!
Membawa daftar 0-diindeks dan output melalui kode keluar.
sumber
Brachylog , 9 byte
Cobalah online!
Predikat berhasil jika input mewakili riffle shuffle dan gagal jika tidak, artinya antara lain jika predikat dijalankan karena seluruh program akan berhasil dicetak
true.
dan kegagalan akan dicetakfalse.
. Input diambil sebagai daftar jenis barang dan menafsirkannya sebagai mewakili permutasi dari dirinya sendiri diurutkan.Saya merasa seperti ada sesuatu dalam semangat
⊆ᵐ
yang harus bekerja di tempat konstruksi "sandwich" empat byte⟨⊆⊇⟩
.sumber
Python 2 ,
756047 byteterima kasih kepada Dennis untuk -13 byte
Cobalah online!
Output melalui kode keluar.
sumber
Ruby , 35 byte
Cobalah online!
Bagaimana?
l & [*1..a] | l
menerapkan persimpangan dan kemudian penyatuan: pertama mendapatkan elemenl
yang ada<=a
dan kemudian menambahkan elemen yang tersisal
tanpa mengubah urutan. Jika a adalah angka yang kami cari, maka operasi ini sama dengan pengurutanl
.sumber
Bersih ,
5655 byteCobalah online!
sumber
Pyth, 5 byte
Suite uji
Cek apakah daftar input dua kali lipat berisi versi diurutkan sendiri sebagai urutan.
Berkat Erik, Outgolfer untuk 1 byte mengambil manfaat yang lebih baik dari input implisit
+QQ
daripada*2Q
.sumber
}SQy+
. Itu akan diperluas ke}SQy+QQ
.Pyth , 9 byte
Suite uji.
Disimpan 3 byte berkat isaacg .
Pyth , 14 byte
Coba di sini! atau Verifikasi semua kasus uji.
Output
True
danFalse
untuk riffle-shuffle dan non-riffle-shuffle.Bagaimana?
sumber
<#0
bisa diganti dengan-
selama 2 byte lagi.Sekam , 7 byte
Suite uji!
sumber
Perl, 28 byte
Termasuk
+1
untuka
Masukan pada STDIN, 1 berbasis
Menggunakan algoritma xnor
sumber
C (gcc) , 61 byte
Cobalah online!
sumber