Bisakah Array tidak diacak?

15

Latar Belakang

Penangan kartu yang sangat terampil mampu melakukan teknik di mana mereka memotong setumpuk menjadi dua sempurna, kemudian dengan sempurna menyisipkan kartu-kartu tersebut. Jika mereka mulai dengan dek yang diurutkan dan melakukan teknik ini dengan sempurna 52 kali berturut-turut, dek akan dikembalikan ke urutan yang diurutkan. Tantangan Anda adalah mengambil setumpuk kartu bilangan bulat dan menentukan apakah kartu itu dapat diurutkan menggunakan hanya Faro shuffles.

Definisi

Secara matematis, Faro shuffle adalah permutasi pada elemen 2 n (untuk bilangan bulat positif n ) yang membawa elemen pada posisi i (1-diindeks) ke posisi 2 i (mod 2 n +1). Kami juga ingin dapat menangani daftar panjang ganjil, jadi dalam hal ini, cukup tambahkan satu elemen ke akhir daftar (Joker, jika Anda memiliki satu berguna) dan Faro mengacak daftar baru seperti di atas, tetapi abaikan elemen dummy yang ditambahkan saat memeriksa pesanan daftar.

Tujuan

Tulis sebuah program atau fungsi yang mengambil daftar bilangan bulat dan mengembalikan atau menampilkan kebenaran jika sejumlah Faro shuffles akan menyebabkan daftar itu diurutkan dalam urutan nondescending (bahkan jika angka itu nol - daftar kecil harus memberikan kebenaran). Jika tidak, kembalikan atau hasilkan falsy.

Contohnya

[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

Mencetak gol

Ini adalah kode-golf sehingga sumber terpendek dalam byte menang.

code-golf array-manipulation permutations kuintopia
sumber
Untuk menghindari kebingungan dengan sesama penangan kartu, perlu dicatat bahwa ada dua jenis pengocokan Faro. In -shuffle dan out-shuffle . Metode yang dijelaskan di sini adalah in-shuffle. Menariknya, hanya perlu 8 out-shuffles untuk mengembalikan setumpuk ke urutan semula. Info Lebih Lanjut
BrainSteel
Bukankah ini hanya "di-acak-acak N + 1 kali dan lihat apakah ada daftar di sepanjang jalan yang diurutkan"?
lirtosiast
Sebenarnya n kali sudah cukup, karena melakukannya 2n kali dijamin untuk menemukan semua permutasi yang mungkin, tetapi Anda akan mendapatkan setidaknya salah satu dari urutan naik atau turun di awal n.
kuintopia
1
Terkait Terkait
Martin Ender
1
bukankah elemen pertama selalu berada di posisi pertama?
Eumel

Jawaban:

3

Pyth - 26 25 24 byte

Gunakan pengurangan kumulatif untuk menerapkan Faro shuffle beberapa kali dan simpan semua hasil. Kemudian, memetakan melalui itu dan memeriksa apakah mereka invarian di bawah pengurutan, kemudian menggunakan jumlah untuk memeriksa apakah ada yang benar. Mengembalikan positif atau nol.

smSI-db.usC_c2NQsC.tc2Qb

Test Suite .

Maltysen
sumber
3

MATL , 41 byte

itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

Outputnya adalah 1atau 0.

Penjelasan

i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

Contoh

>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1
Luis Mendo
sumber