Input: Dua bilangan bulat n dan k diberikan dalam bentuk apa pun yang sesuai untuk kode Anda
Keluaran Urutan bilangan bulat k yang tidak menurun secara acak, masing-masing dalam kisaran 1 hingga n. Sampel harus dipilih secara seragam dari semua urutan non-pengurangan dari bilangan bulat k dengan bilangan bulat dalam kisaran 1 sampai n.
Outputnya bisa dalam format apa pun yang Anda rasa nyaman.
Anda dapat menggunakan generator pseudo-acak apa pun yang disediakan oleh perpustakaan / bahasa favorit Anda.
Kita dapat mengasumsikan bahwa bilangan bulat n, k> 0.
Contoh
Katakan n, k = 2. Urutan non-menurun adalah
1,1
1,2
2,2
Setiap urutan harus memiliki probabilitas 1/3 untuk di-output.
Larangan
Kode Anda harus berjalan dalam tidak lebih dari beberapa detik untuk k = 20 dan n = 100.
Apa yang tidak berhasil?
Jika Anda hanya mengambil sampel setiap bilangan bulat secara acak dari rentang 1 hingga n dan kemudian mengurutkan daftar Anda tidak akan mendapatkan distribusi yang seragam.
sumber
Jawaban:
Sebenarnya ,
1412 byteJawaban ini didasarkan pada jawaban 05AB1E Emigna dan jawaban untuk pertanyaan Math.SE ini . Selamat datang saran bermain golf! Cobalah online!
Tidak melakukanolf
sumber
Python, 89 byte
Menghasilkan urutan yang meningkat daripada yang tidak menurun akan langsung: ini hanya bagian acak dari
k
angka antara1
dann
, diurutkan.Tapi, kita bisa mengonversi urutan yang meningkat menjadi yang tidak berkurang dengan mengecilkan setiap celah antara angka berurutan dengan 1. Jadi, celah 1 menjadi celah 0, membuat angka sama. Untuk melakukannya, kurangi nilai
i
terbesar kei
Agar hasilnya dari
1
ken
, input harus dari1
ken+k-1
. Ini memberikan sebuah penipisan antara urutan nomor yang tidak menurun antara1
dann
, untuk meningkatkan urutan antara1
dann+k-1
. Bijection yang sama digunakan dalam argumen bintang dan balok untuk menghitung urutan tersebut.Kode menggunakan fungsi python
random.sample
, yang mengambilk
sampel tanpa penggantian dari daftar input. Menyortirnya memberikan urutan meningkat.sumber
import*
dapat menyimpan 1 byte)05AB1E , 13 byte
Cobalah online!
Penjelasan
sumber
Python, 87 byte
Probabilitas bahwa nilai maksimum yang mungkin
n
dimasukkan sama dengank/(n+k-1)
. Untuk memasukkannya, letakkan di akhir daftar, dan kurangi jumlah yang diperlukank
. Untuk mengecualikannya, kurangi batas atasn
. Kemudian, ulangi sampai tidak ada lagi nilai yang diperlukan (k==0
).Python
random
tampaknya tidak memiliki built-in untuk variabel Bernoulli: 1 dengan beberapa probabilitas, dan 0 sebaliknya. Jadi, ini memeriksa apakah nilai acak antara 0 dan 1 yang dihasilkan olehrandom
jatuh di bawah inik/(n+k-1)
. Python 2 akan rasio sebagai divisi float, jadi kami bukan kalikan dengan penyebut:k>random()*(n+k-1)
.sumber
numpy.random
, yang terlalu panjang.JavaScript (Firefox 30+), 74 byte
Penjelasan
Jawaban Python xnor yang sangat baik berisi ringkasan yang sangat bagus tentang bagaimana / mengapa teknik yang digunakan di sini bekerja. Langkah pertama adalah membuat rentang [1, 2, ..., n + k - 1] :
Selanjutnya kita perlu mengambil k item acak dari kisaran ini. Untuk melakukan ini, kita perlu memilih setiap item dengan probabilitas s / q , di mana s adalah jumlah item yang masih dibutuhkan dan q adalah jumlah item yang tersisa dalam rentang. Karena kami menggunakan pemahaman array, ini cukup mudah:
Ini memberi kita terdistribusi secara merata meningkatkan urutan angka. Ini dapat diperbaiki dengan mengurangi jumlah item j yang sebelumnya kami temukan:
Akhirnya, dengan menyimpan k dalam j , kita dapat memasukkan
k--
ke dalam ekspresi dan menyimpan beberapa byte:sumber
TI-BASIC, 54 Bytes
Ikuti logika xnor, dengan peringatan kecil. Secara teoritis kita bisa mencukur byte dengan melakukan sesuatu seperti ini:
Tetapi rand (dicadangkan untuk membuat daftar angka acak, jadi kami tidak akan dapat melakukan perkalian implisit yang diinginkan untuk menyimpan byte.
Ini harus berjalan dengan cepat pada 84+ per pembatasan tetapi saya akan memeriksa untuk memastikan kapan saya bisa.
sumber
PHP,
777573 byteJalankan seperti ini:
Penjelasan
Tweaks
end()
panggilan dan set$argv[2]
untuk$k
bukan untuk akses mempersingkat argumen$i
setiap iterasi sajasumber