Cicipi urutan acak yang tidak menurun

20

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.

DJMcMayhem
sumber
Menghasilkan jumlah urutan yang tidak berkurang untuk n, k mungkin membuat tantangan yang menarik sendiri, jika belum dilakukan ...
ETHproduksi
1
@ ETHproductions Tidak juga, itu hanya binomial (terkait dengan ini )
Sp3000
@ Sp3000 Ah, oke. Itu adalah tantangan yang menyenangkan bagi saya untuk mencari cara menghitungnya secara efisien.
ETHproduksi
Persyaratan Anda bahwa setiap urutan memiliki probabilitas yang sama untuk keluaran tidak mungkin dipenuhi dengan sebagian besar varietas taman PRNG yang mungkin hanya memiliki status 32 atau 48 bit. Menurut Wolfram, ada 535 trilyun 20 elemen berikutnya dari 1, ..., 100 (tidak memeriksa berapa banyak dari mereka yang tidak meningkat). 2 ^ 64 hanya 18 triliun.
Sinan Ünür

Jawaban:

1

Sebenarnya , 14 12 byte

Jawaban ini didasarkan pada jawaban 05AB1E Emigna dan jawaban untuk pertanyaan Math.SE ini . Selamat datang saran bermain golf! Cobalah online!

;;ra+DR╚HS♀-

Tidak melakukanolf

      Implicit input n, then k.
;;    Duplicate k twice.
r     Push range [0...k] for later.
a     Invert the stack. Stack: n, k, k, [0...k]
+DR   Push the range [1..n+k-1].
╚     Shuffle the range. Stack: shuffled_range, k, [0...k]
H     Push the first k elements of shuffled_range. Call this increasing.
S     Sort increasing so the elements are actually increasing.
♀-    Subtract each element of [0...k] from each element of increasing.
      This gives us our non-decreasing sequence.
      Implicit return.
Sherlock9
sumber
13

Python, 89 byte

from random import*
lambda n,k:[x-i for i,x in enumerate(sorted(sample(range(1,n+k),k)))]

Menghasilkan urutan yang meningkat daripada yang tidak menurun akan langsung: ini hanya bagian acak dari kangka antara 1dan n, 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 iterbesar kei

r[0], r[1], ..., r[n-1]  =>  r[0]-0, r[1]-1, ..., r[n-1]-(n-1)

Agar hasilnya dari 1ke n, input harus dari 1ke n+k-1. Ini memberikan sebuah penipisan antara urutan nomor yang tidak menurun antara 1dan n, untuk meningkatkan urutan antara 1dan n+k-1. Bijection yang sama digunakan dalam argumen bintang dan balok untuk menghitung urutan tersebut.

Kode menggunakan fungsi python random.sample, yang mengambil ksampel tanpa penggantian dari daftar input. Menyortirnya memberikan urutan meningkat.

Tidak
sumber
Ini mengesankan. Bisakah Anda menambahkan penjelasan tentang metode ini?
Yup, sibuk sekarang, akan jelaskan nanti.
xnor
Saya menghitung 90 byte ... (dan Anda juga import*dapat menyimpan 1 byte)
Rod
@Rod Terima kasih, saya lupa tentang itu.
xnor
7

05AB1E , 13 byte

+<L.r¹£{¹L<-Ä

Cobalah online!

Penjelasan

+<L            # range [1 ... n+k-1]
   .r          # scramble order
     ¹£        # take k numbers
       {       # sort
        ¹L<-   # subtract from their 0-based index
            Ä  # absolute value
Emigna
sumber
7

Python, 87 byte

from random import*
f=lambda n,k:k>random()*(n+k-1)and f(n,k-1)+[n]or k*[7]and f(n-1,k)

Probabilitas bahwa nilai maksimum yang mungkin ndimasukkan sama dengan k/(n+k-1). Untuk memasukkannya, letakkan di akhir daftar, dan kurangi jumlah yang diperlukan k. Untuk mengecualikannya, kurangi batas atas n. Kemudian, ulangi sampai tidak ada lagi nilai yang diperlukan ( k==0).

Python randomtampaknya 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 oleh randomjatuh di bawah ini k/(n+k-1). Python 2 akan rasio sebagai divisi float, jadi kami bukan kalikan dengan penyebut: k>random()*(n+k-1).

Tidak
sumber
Apakah numpy akan membantu di sini?
@Lembik Pemikiran bagus, tetapi sepertinya Anda harus mengimpor numpy.random, yang terlalu panjang.
xnor
5

JavaScript (Firefox 30+), 74 byte

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]

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] :

(n,k,i=0)=>[for(_ of Array(q=k+n-1))++i]

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:

(n,k,i=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i]

Ini memberi kita terdistribusi secara merata meningkatkan urutan angka. Ini dapat diperbaiki dengan mengurangi jumlah item j yang sebelumnya kami temukan:

(n,k,i=0,j=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i-j++]

Akhirnya, dengan menyimpan k dalam j , kita dapat memasukkan k--ke dalam ekspresi dan menyimpan beberapa byte:

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]
Produksi ETH
sumber
2

TI-BASIC, 54 Bytes

Prompt N,K
K→dim(L1
While K
If rand<K/(N+K-1
Then
N→L1(K
K-1→K
Else
N-1→N
End
End
Disp L1

Ikuti logika xnor, dengan peringatan kecil. Secara teoritis kita bisa mencukur byte dengan melakukan sesuatu seperti ini:

K>rand(N+K-1

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.

TiKevin83
sumber
1

PHP, 77 75 73 byte

foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;

Jalankan seperti ini:

php -r 'foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;' -- 10 5 2>/dev/null;echo
> 1_4_6_9_9_

Penjelasan

foreach(                    # Iterate over...
  array_rand(               #   a (sorted) random number of items from...
    range(                  #     an array with items...
      2,                    #       from 2
      $argv[1]+$k=$argv[2]  #       to n + k (set arg 2 to $k)
    ),
    $k                      #     Take k number of items (their keys)
  )
  as $v
)
  echo $v +1 - $i++,"_";    # Print the value subtracted by the index.
                            # Need to add 1, because keys are 0-indexed.

Tweaks

  • Disimpan 2 byte dengan menghapus end()panggilan dan set $argv[2]untuk $kbukan untuk akses mempersingkat argumen
  • Disimpan 2 byte dengan menghapus indeks dari foreach, karena itu hanya angka yang bertambah. Cukup tambahkan $isetiap iterasi saja
aross
sumber
JavaScript pertama dan sekarang PHP. Semua bahasa pemrograman ilmiah terbaik :) Terima kasih.
@Lembik, sama-sama. Pikiran Anda, ia menggunakan PRNG dasar. Jangan gunakan untuk hal-hal kriptografis . :)
aross