Apakah ini acak?

19

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,2memiliki urutan relatif yang sama untuk setiap kartu lain di partisi itu. 2masih 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 1dan 2ubah urutannya, sedangkan di partisi kedua 2dan 3ubah 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 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
Wisaya Gandum
sumber
1
Bisakah hasilnya tidak konsisten, tetapi benar / salah dalam bahasa kita? Seperti (Python, di mana, di antara bilangan bulat hanya 0 adalah falsy) 0untuk falsy tetapi bilangan bulat apa pun [1, +∞)untuk kebenaran?
Tn. Xcoder
1
@ Mr.Xcoder Saya tidak suka nilai kebenaran / kepalsuan karena agak sulit untuk didefinisikan dengan baik. Jawaban harus berpegang pada aturan saat ini.
Wheat Wizard
Kasus uji yang disarankan: [3,1,4,2,5].
Ørjan Johansen
9
Maaf tentang ini, tapi: [2,3,6,1,4,5].
Ørjan Johansen
1
Bisakah kita mengambil permutasi [0, ..., n-1]alih-alih [1, ..., n]sebagai input?
Dennis

Jawaban:

8

JavaScript (ES6), 47 byte

Mengambil input sebagai array bilangan bulat. Mengembalikan boolean.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Uji kasus

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:

  • Kami memeriksa apakah z sama dengan x + 1 atau y + 1 . Jika ya, kami menambah penghitung yang sesuai.
  • Lain: jika y masih belum ditentukan, kita inisialisasi ke z .
  • Lain: kita membuat tes gagal.
Arnauld
sumber
6

Haskell , 41 byte

n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

Cobalah online!

Cek apakah daftar yang disatukan dengan dirinya sendiri berisi angka-angka 0..n-1sebagai urutan.

Tidak
sumber
5

Haskell , 43 byte

smengambil daftar bilangan bulat seperti pada contoh OP dan mengembalikan a Bool.

s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

Cobalah online!

Bagaimana itu bekerja

  • Daftar pemahaman mencoba setiap elemen xdari ppada gilirannya dan cek jika dapat menjadi elemen pertama dari partisi kedua shuffle. Kemudian orkembali Truejika ada cek True.
  • Pemahaman melakukan ini dengan mempartisi (dengan filter) pke 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.
  • Periksa apakah daftar yang dihasilkan [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.
Ørjan Johansen
sumber
5

Jelly , 13 6 byte

ỤIṢḊRẠ

Cobalah online!

Versi alternatif, tantangan tanggal kiriman, 5 byte

Ụ>ƝSỊ

Cobalah online!

Bagaimana itu bekerja

ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.
Dennis
sumber
5

Python 2 , 39 byte

l=input()
n=0
for x in l*2:n+=n==x
l[n]

Cobalah online!

Membawa daftar 0-diindeks dan output melalui kode keluar.

Tidak
sumber
4

Brachylog , 9 byte

o~cĊ⟨⊆⊇⟩?

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 dicetak false.. Input diambil sebagai daftar jenis barang dan menafsirkannya sebagai mewakili permutasi dari dirinya sendiri diurutkan.

   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

Saya merasa seperti ada sesuatu dalam semangat ⊆ᵐyang harus bekerja di tempat konstruksi "sandwich" empat byte ⟨⊆⊇⟩.

String yang tidak terkait
sumber
1
Saya pikir Anda adalah orang pertama yang menggunakan sandwich dalam jawaban PPCG (dan ini sangat simetris :))
Fatalize
3

Python 2 , 75 60 47 byte

terima kasih kepada Dennis untuk -13 byte

x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

Cobalah online!

Output melalui kode keluar.

ovs
sumber
2

Ruby , 35 byte

->l{l.any?{|a|l&[*1..a]|l==l.sort}}

Cobalah online!

Bagaimana?

  • l & [*1..a] | lmenerapkan persimpangan dan kemudian penyatuan: pertama mendapatkan elemen lyang ada <=adan kemudian menambahkan elemen yang tersisa ltanpa mengubah urutan. Jika a adalah angka yang kami cari, maka operasi ini sama dengan pengurutan l.
GB
sumber
2

Pyth, 5 byte

}SQy+

Suite uji

}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 

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 +QQdaripada *2Q.

Tidak
sumber
5 byte: }SQy+. Itu akan diperluas ke }SQy+QQ.
Erik the Outgolfer
@EriktheOutgolfer Bagus, terima kasih.
xnor
1

Pyth , 9 byte

!t-.+xLQS

Suite uji.

Disimpan 3 byte berkat isaacg .

Pyth , 14 byte

}SQm.nS.Tcd2./

Coba di sini! atau Verifikasi semua kasus uji.

Output Truedan Falseuntuk riffle-shuffle dan non-riffle-shuffle.

Bagaimana?

} SQm.nS.Tcd2./ ~ Program lengkap. Membaca input dari STDIN dan output ke STDOUT.

            ./ ~ Kembalikan semua divisi input ke substring terpisah (partisi).
   m ~ Peta di atas menggunakan variabel d.
         cd2 ~ Potong d menjadi daftar dua elemen.
       .T ~ Membenarkan transposisi, mengabaikan absen.
      S ~ Sortir (leksikografis).
    .n ~ Diratakan rata.
} ~ Periksa apakah di atas mengandung ...
 SQ ~ Input yang diurutkan.
Tuan Xcoder
sumber
Selanjutnya, <#0bisa diganti dengan -selama 2 byte lagi.
isaacg
@isaacg Oh ya facepalm terima kasih. Diedit. Diedit.
Tn. Xcoder
0

Sekam , 7 byte

±§#OoṖD

Suite uji!

Tuan Xcoder
sumber
0

Perl, 28 byte

Termasuk +1untuka

Masukan pada STDIN, 1 berbasis

perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Menggunakan algoritma xnor

Ton Hospel
sumber
0

C (gcc) , 61 byte

a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

Cobalah online!

Jonathan Frech
sumber