Pilih angka acak antara 0 dan n menggunakan sumber acak yang konstan

26

Tugas

Diberikan bilangan bulat positif nkurang dari yang 2^30ditentukan sebagai input dengan cara apa pun yang Anda pilih, kode Anda harus menghasilkan bilangan bulat acak antara 0dan n, termasuk. Angka yang Anda hasilkan harus dipilih secara acak . Itu adalah setiap nilai dari 0hingga nharus terjadi dengan probabilitas yang sama (lihat Aturan dan Peringatan).

Aturan dan Peringatan

Kode Anda dapat mengasumsikan bahwa setiap generator angka acak yang dibangun ke dalam bahasa Anda atau pustaka standar yang mengklaimnya acak secara acak sebenarnya seragam. Itu adalah Anda tidak perlu khawatir tentang kualitas sumber acak yang Anda gunakan. Namun,

  • Anda harus menetapkan bahwa jika sumber acak yang Anda gunakan adalah seragam maka kode Anda dengan benar menghasilkan integer acak seragam dari 0ke n.
  • Argumen apa pun saat memanggil fungsi bawaan atau pustaka acak harus konstan. Itu mereka harus sepenuhnya independen dari nilai input.
  • Kode Anda dapat berakhir dengan probabilitas 1 daripada dijamin untuk berakhir.

Catatan

  • randInt(0,n) tidak valid karena mengambil input sebagai argumen ke fungsi builtin atau library.
  • rand()%ntidak akan memberikan nomor acak seragam pada umumnya. Sebagai contoh yang diberikan oleh betseg, jika intmax == 15dan n = 10, maka Anda akan jauh lebih mungkin mendapatkan 0-5daripada 6-10.
  • floor(randomfloat()*(n+1)) juga tidak akan memberikan angka acak seragam pada umumnya karena jumlah terbatas dari nilai floating point yang mungkin antara 0 dan 1.
benar-benar manusiawi
sumber
Bagaimana Anda akan mengkonfirmasi bahwa output acak acak? Mungkin bahasa / pustaka yang diberikan akan menampilkan angka acak yang seragam, tetapi manipulasi dapat menghasilkan keluaran yang tidak seragam. (mis. rng()memberikan 0- 100, jika n = 75, dan fungsinya adalah rng()%75, maka 0-25 akan lebih umum ...)
Baldrickk
1
@Baldrickk Dengan kebijaksanaan orang banyak :) Kita hanya bisa membaca kode dan memikirkannya.
Kesimpulan menyedihkan mengajukan pertanyaan probabilitas-teori paling sederhana: keacakan dan probabilitas sangat kurang dipahami. :( (Dan aturan membaca sulit, rupanya.)
Martin Ender
Ini terlintas dalam pikiran: Nomor Acak
BgrWorker
Mengapa Anda menerima jawaban x86 ketika ada tiga yang lebih pendek?
Dennis

Jawaban:

25

mesin x86 dengan rdrandinstruksi, 10 byte

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

kode mesin

0FC7F0 73FB 39F8 77F7 C3

Input ada di register rdidan output di rax.
Ini menghormati SYS V AMD64 ABI sehingga kode secara efektif mengimplementasikan fungsi C

unsigned int foo(unsigned int max); 

dengan int 32-bit.

Instruksi rdranddijelaskan oleh Intel

RDRANDmengembalikan nomor acak yang dipasok oleh DRBG bit acak acak yang deterministik aman. DRBG dirancang untuk memenuhi standar NIST SP 800-90A .

Berhubungan dengan CSRNG, implisit bahwa distribusinya seragam, mengutip NIST SP 800-90A:

Angka acak adalah turunan dari variabel acak yang tidak bias, yaitu, output yang dihasilkan oleh proses acak yang terdistribusi secara merata .


Prosedur ini menghasilkan angka acak dan jika tidak benar-benar lebih besar dari input itu dikembalikan.
Jika tidak, proses akan diulangi lagi.

Karena eax32-bit, rdrandmengembalikan angka antara 0 dan 2 32 -1, jadi untuk setiap n di [0, 2 32 -1] jumlah iterasi yang diharapkan adalah 2 32 / (n + 1) yang didefinisikan untuk semua n dalam [0, 2 30 ).

Margaret Bloom
sumber
Tingkat sangat rendah. Terima kasih.
Untuk apa ini jnc?
14m2
@ l4m2 rdrandmenetapkan bahwa CFjika data yang dikembalikan valid. Data mungkin tidak valid karena terlalu banyak permintaan mengeringkan kumpulan entropi. Lihat entri manual untuk rdrand dan ini .
Margaret Bloom
20

Jelly , 7 6 byte

⁴!!X%‘

Terima kasih kepada @JonathanAllan untuk bermain golf 1 byte!

Tidak dapat dijalankan di TIO karena (16!)! adalah jumlah yang sangat besar .

Bagaimana itu bekerja

⁴!!X%‘  Main link. Argument: n

⁴       Set the return value to 16.
 !!     Compute (16!)!.
   X    Pseudo-randomly choose an integer between 1 and (16!)!.
        Since (16!)! is evenly divisible by any k ≤ 2**30, it is evenly divisible
        by n+1.
    %‘  Take the result modulo n+1.
Dennis
sumber
Ini adalah versi tetap dari jawaban saya yang dihapus, ide yang sama. Meskipun saya memang memiliki eksponen yang tidak perlu.
orlp
Maaf, saya tidak melihatnya sebelum memposting.
Dennis
Oh itu tidak masalah, saya tidak berencana memperbaikinya. Saya terlalu tidak nyaman dengan Jelly untuk bermain-main dengannya.
orlp
1
"Pak, saya tidak tahu mengapa Anda marah. Algoritma ini adalah waktu yang konstan. Itu hal yang baik, bukan? Mengapa keamanan dan SDM di luar pintu?"
corsiKa
1
Sepakat. Sedikit perbedaan antara angka 8 digit dan angka 417 trilyun digit: p
Jonathan Allan
11

Mathematica, 29 byte

Berdasarkan jawaban Dennis's Jelly .

RandomInteger[2*^9!-1]~Mod~#&

Saya tidak akan merekomendasikan untuk menjalankan ini. 2e9!adalah jumlah yang cukup besar ...

Ternyata menjadi yang terpendek untuk menghasilkan sejumlah besar yang dapat dibagi oleh semua input yang mungkin dan memetakan hasilnya ke kisaran yang diperlukan dengan modulo sederhana.

Sampel Penolakan, 34 byte

Pendekatan lama saya yang menghasilkan kode yang lebih menarik:

13!//.x_/;x>#:>RandomInteger[13!]&

Pengambilan sampel penolakan dasar. Kami menginisialisasi output ke 13! (yang lebih besar dari input maksimum 2 30 ) dan kemudian menggantinya berulang kali dengan integer acak antara 0 dan 13! asalkan nilainya lebih besar dari input.

Martin Ender
sumber
1
Apakah maksud Anda "lebih kecil dari atau sama dengan input"?
1
@Lembik No. Kami ingin membuat ulang nilai selama tidak masuk dalam rentang yang diinginkan.
Martin Ender
Oh begitu. Untuk beberapa alasan saya pikir kami berulang kali mengambil sampel dari kisaran yang diinginkan. Terima kasih.
1
Ingatkan saya untuk menambahkan batas waktu nanti :)
9

Brachylog , 9 byte

≥.∧13ḟṙ|↰

Cobalah online!

Ini menggunakan 13!seperti dalam jawaban Martin Ender ( 13ḟkurang dari satu byte 2^₃₀).

diimplementasikan menggunakan random_between/3, yang, ketika menggali sumbernya, menggunakan random_float/0yang terkait dengan random/1yang menggunakan algoritma Mersenne Twister yang seragam untuk tujuan kami.

Penjelasan

≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input
Fatalisasi
sumber
7

Prolog (SWI) , 38 byte

X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.

Bekerja dengan sampel penolakan.

Hasilkan angka acak antara 0 dan 2 ^ 31-1 = 2147483647 hingga ditemukan kurang dari atau sama dengan input.

Saya merasa seolah-olah saya bisa menggunakan potongan daripada yang lain, tapi saya tidak bisa melihat caranya.

Emigna
sumber
1
Anda bisa menghindari yang lain menggunakan repeat, tetapi akhirnya menjadi 3 byte lebih lama ... Saya tidak yakin apakah ada cara yang lebih pendek untuk memiliki poin pilihan yang tak terbatas daripada mengulang.
Fatalkan
@Fatalize: Ya saya coba ulangi juga. Saya memiliki memori menggunakan sesuatu seperti ,!.untuk memaksa mundur, tetapi entah saya salah mengingatnya atau itu tidak berlaku untuk solusi ini.
Emigna
7

Labirin , 63 byte

 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#

(Terima kasih kepada @MartinEnder untuk bantuan bermain golf berat di sini.)

Labyrinth adalah bahasa 2D, dan satu-satunya sumber keacakan dalam situasi seperti berikut:

   x
  "<)
 " "
 " "

Asumsikan pointer instruksi ada di xdan bergerak ke bawah. Selanjutnya mendarat di <, yang jika bagian atas tumpukan adalah 0 (yang selalu terjadi dalam program aktual di atas) menggeser baris saat ini ditinggalkan oleh 1:

   "
 "<)
 " "
 " "

Penunjuk instruksi sekarang <bergerak ke bawah. Di persimpangan, Labyrinth belok berdasarkan bagian atas tumpukan - negatif belok kiri, positif belok kanan dan nol bergerak maju. Jika bagian atas tumpukan masih nol pada titik ini, kita tidak dapat bergerak maju atau mundur karena tidak ada jalur, sehingga Labirin akan mengacak antara belok kiri atau belok kanan dengan probabilitas yang sama.

Pada dasarnya apa yang dilakukan oleh program di atas adalah menggunakan fitur keacakan untuk menghasilkan angka 100-bit (100 ditentukan di #00sini) dan melanjutkan perulangan hingga menghasilkan angka <= n.

Untuk pengujian, mungkin akan lebih baik digunakan #0"untuk angka 10-bit, dengan "menjadi jalur no-op. Cobalah online!

Penjelasan kasar:

 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#

 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.
Sp3000
sumber
7

Python, 61 byte

from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)

Sunting: Diperbarui untuk menghindari formulir terlarang

Sunting2: Disimpan 2 byte, terima kasih @ JonathanAllan

Sunting3: Dibayar 2 byte untuk solusi yang berfungsi penuh - terima kasih lagi @JonathanAllan

Sunting4: Dihapus f=, menyimpan 2 byte

Sunting5: Disimpan 1 byte lebih banyak berkat @ JonathanAllan

Sunting6: Disimpan 2 byte lebih banyak berkat @ JonathanAllan

Sekarang, git menyalahkan akan menunjuk pada saya untuk hal-hal buruk, dan Jonathan Allan untuk hal-hal yang membantu.

Sunting7: Saat hujan, itu menuangkan - 2 byte lagi

Sunting8: Dan 2 byte lagi

iwaseatenbyagrue
sumber
1
Ini tidak akan pernah menghasilkan n, tetapi Anda dapat menyimpan dua byte saat Anda memperbaikinya dengan menggunakan from random import*dan menjatuhkan r..
Jonathan Allan
1
Ya, Anda dapat menggunakan "operator berudu" untuk menghindari tanda kurung yang diperlukan, jadi ...*(-~n*1.0/2**30))daripada...*((n+1)*1.0/2**30))
Jonathan Allan
1
Sangat? Manis! Apakah Anda memiliki dendam lama terhadap nomor 70? Terima kasih banyak atas bantuan Anda
iwaseatenbyagrue
1
Bahkan randrangetampaknya menerima float, jadi lambda n,x=2.**30:int(randrange(x)*-~n/x)simpan dua [edit ...] empat!
Jonathan Allan
1
^ dua lagi di sana dengan penghapusan tanda kurung. Hanya pergi untuk menunjukkan penggandaan Anda adalah cara untuk pergi!
Jonathan Allan
6

Python 2 , 61 byte

from random import*
lambda n:map(randrange,range(1,2**31))[n]

Pseudo-acak memilih integer antara 0 dan k untuk semua nilai k antara 0 dan 2 31 - 2 , kemudian mengambil integer yang sesuai dengan k = n .

Dennis
sumber
5

Batch, 64 byte

@set/ar=%random%*32768+%random%
@if %r% gtr %1 %0 %1
@echo %r%

%random%hanya memberikan 15 bit keacakan, jadi saya harus menggabungkan dua angka acak. Putaran sampai nilai acak berada dalam kisaran yang diinginkan, jadi lambat untuk rendah n; 98 byte untuk versi yang lebih cepat:

@set/a"n=%1+1,m=~(3<<30)/n*n,r=%random%*32768+%random%
@if %r% geq %m% %0 %1
@cmd/cset/a%r%%%%n%
Neil
sumber
Kode mungkin lambat tetapi jawaban Anda cepat!
3
@Lembik Saya sudah siap menjawab pertanyaan yang dihapus ...
Neil
Tidakkah ini akan menggemakan angka yang diinginkan terlebih dahulu, dan kemudian semua angka lain yang berubah menjadi lebih besar dari n?
Erik the Outgolfer
@EriktheOutgolfer No; kecuali Anda menggunakannya call, menjalankan skrip batch akan menghentikan skrip saat ini.
Neil
5

MATL , 12 byte

Terima kasih kepada @AdmBorkBork dan @Suever karena memberi tahu saya cara menonaktifkan cache TIO.

`30WYrqG>}2M

Cobalah online! .

Ini menggunakan metode penolakan : menghasilkan bilangan bulat acak dari 0ke 2^30-1, dan ulangi saat melebihi input n. Ini dijamin untuk berakhir dengan probabilitas 1, tetapi jumlah rata-rata iterasi adalah 2^30/n, dan karena itu sangat lama untuk nsecara signifikan lebih kecil daripada 2^30.

`         % Do...while
  30W     %   Push 2^30
  Yr      %   Random integer from 1 to 2^30
  q       %   Subtract 1
  G>      %   Does it exceed the input? If so: next iteration. Else: exit
}         % Finally (execute right before exiting the loop)
  2M      %   Push the last generated integer
          % End (implicit). Display (implicit)
Luis Mendo
sumber
4

JavaScript (ES6), 55 54 byte

f=(n,m=1)=>m>n?(x=Math.random()*m|0)>n?f(n):x:f(n,m*2)

Menghasilkan bilangan bulat dalam kisaran [0 ... 2 k - 1] , di mana k adalah bilangan bulat terkecil sehingga 2 k lebih besar dari n . Ulangi sampai hasilnya jatuh ke [0 ... n] .

Mengapa?

Ini didasarkan pada asumsi berikut:

  • Secara internal, nilai integer pseudo-acak yang dihasilkan oleh mesin JS untuk memberi makan Math.random()seragam pada setiap interval [0 ... 2 k -1] (dengan k <32 ).

  • Setelah dikalikan dengan kekuatan tepat 2, nilai float IEEE 754 yang dikembalikan oleh Math.random()masih seragam selama interval tersebut.

Jika ada yang bisa mengkonfirmasi atau membantah hipotesis ini, beri tahu saya di komentar.

Demo

Menghasilkan 1 juta nilai dalam [0 ... 2] dan menampilkan statistik hasil.

Arnauld
sumber
Math.floor (Math.random () * (n +1)) menghasilkan hasil yang tidak kurang merata bagi saya, jadi alangkah baiknya jika ada N <2 ^ 30 yang realistis, yang akan menghasilkan anomali distribusi apa pun. sama sekali.
zeppelin
1
@zeppelin Anda akan memerlukan terlalu banyak percobaan untuk menentukan setiap anomali karena float acak dalam rentang itu akan memiliki salah satu dari 2 ^ 53 nilai yang akan didistribusikan secara merata mungkin selama 2 ^ 30 hasil. Jadi, bahkan untuk jumlah besar dalam kisaran tersebut, kesalahannya akan menjadi sekitar 1 dalam 2 ^ 23 yang berarti Anda akan memerlukan sejumlah percobaan yang konyol. Anda mungkin ingin beberapa kali lipat lebih besar daripada jumlah sampel awal (2 ^ 53). Namun demikian, itu tidak bisa seragam sempurna jika pengganda tidak membagi jumlah sampel secara merata, itulah sebabnya Arnauld menggunakan kekuatan dua.
Martin Ender
4

Bash (+ coreutils), 44 byte

/ dev / solusi berbasis urandom

od -w4 -vtu4</d*/ur*|awk '($0=$2)<='$1|sed q

Akan membaca bilangan bulat 32 bit yang tidak ditandatangani dari /dev/urandom, dan menyaringnya awksampai menemukan satu dalam kisaran yang diberikan, kemudian sed qakan membatalkan pipa.

zeppelin
sumber
Hore untuk pesta :)
4

Haskell, 70 byte

import System.Random
g n=head.filter(<=n).randomRs(0,2^30)<$>getStdGen

Bukan algoritma yang sangat efisien tetapi berhasil. Ini menghasilkan daftar bilangan bulat tak terbatas (atau mengapung jika diperlukan, karena sistem tipe Haskell) yang dibatasi oleh [0,2 ^ 30] dan mengambil yang pertama kurang dari atau sama dengan n. Untuk kecil dan ini bisa memakan waktu lama. Angka-angka acak harus didistribusikan secara seragam, seperti yang ditentukan dalam dokumentasi untuk randomR sehingga semua angka dalam interval [0,2 ^ 30] harus memiliki probabilitas yang sama (1 / (2 ^ 30 + 1)) karena itu semua angka dalam [ 0, n] memiliki probabilitas yang sama.

Versi Alternatif:

import System.Random
g n=head.filter(<=n).map abs.randoms<$>getStdGen

Versi ini mengerikan tetapi menyimpan seluruh byte. randomsmenggunakan rentang sewenang-wenang yang ditentukan oleh tipe untuk menghasilkan daftar angka yang tak terbatas. Ini mungkin termasuk negatif sehingga kita perlu memetakannya absuntuk memaksa mereka positif (atau nol). Ini sangat lambat untuk nilai n yang tidak terlalu besar. EDIT : Saya menyadari kemudian bahwa versi ini tidak terdistribusi secara seragam karena kemungkinan mendapatkan 0 lebih buruk daripada angka-angka lain karena penggunaan abs. Untuk menghasilkan beberapa angka m, generator dapat menghasilkan matau -mtetapi dalam kasus 0 hanya 0 itu sendiri yang akan bekerja, oleh karena itu probabilitasnya adalah setengah dari angka lainnya.

pengguna1472751
sumber
Hore untuk Haskell (juga)!
4

Jelly , 9 byte

⁴!Ẋ’>Ðḟ⁸Ṫ

Cobalah online! - kode di atas tidak akan berjalan pada TIO karena kisaran ukuran 16! harus dibangun terlebih dahulu (belum lagi fakta bahwa mereka kemudian perlu dikocok dan kemudian disaring!), jadi ini adalah hal yang sama pada skala yang jauh lebih kecil, diulang 30 kali untuk input 3 dengan batas 10.

Bagaimana?

⁴!Ẋ’>Ðḟ⁸Ṫ - Main link: n
⁴         - 16
 !        - factorial: 20922789888000
  Ẋ       - shuffle random: builds a list of the integers 1 through to 16! inclusive and
          - returns a random permutation via Python's random.shuffle (pretty resource hungry)
   ’      - decrement (vectorises - a whole pass of this huge list!)
     Ðḟ   - filter out if: (yep, yet another pass of this huge list!)
    >     -     greater than
       ⁸  -     left argument, n
        Ṫ - tail: return the rightmost remaining entry.

Catatan: akan lebih dari seribu kali lebih efisien untuk jumlah byte yang sama jika ȷ⁵melakukan apa yang diharapkan secara naif dan mengembalikan sepuluh ke sepuluh, tetapi itu tidak terjadi karena tidak dievaluasi sebagai sepuluh literal yang akan digunakan dengan angka literal ȷ...tetapi lebih dari dua literal yang terpisah diurai, ȷdengan eksponen default tiga menghasilkan seribu, dan menghasilkan sepuluh.

Jonathan Allan
sumber
Huh, itu 9 karakter, tetapi 22 byte
Kristoffer Sall-Storgaard
@ KristofferSall-Storgaard Setiap karakter adalah salah satu dari 256 byte di halaman kode Jelly , saya lupa membuat kata byte sebagai tautan seperti yang biasa saya lakukan.
Jonathan Allan
1
tahun, saya mencarinya dan menemukan hal yang sama
Kristoffer Sall-Storgaard
4

JDK 9 on jshell, 75 59 byte

n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny()

Pemakaian

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 byte: Terima kasih Jakob!
  • Asumsikan bahwa kami menganggap jshell sebagai lingkungan runtime yang valid.
  • jshell sendiri, sebagai lingkungan runtime, tidak memerlukan impor eksplisit untuk pustaka inti dan tidak memerlukan titik koma.
  • Mengembalikan sebuah OptionalInt. Aturan tidak menentukan bahwa tipe pengembalian harus primitif dan saya mempertimbangkan OptionalIntuntuk menjadi representasi hasil yang valid.
Pete Terlep
sumber
1
Terima kasih kepada @ kevin-cruijssen untuk inspirasinya. Golf kode pertama saya!
Pete Terlep
Apakah output kotak diterima atau tidak berbeda dengan apakah suatu Optionalditerima. Saya akan mengkonfirmasi dengan poster jika saya adalah Anda. Juga, tidak perlu menghitung seluruh penugasan; hanya ungkapan lambda yang cukup.
Jakob
1
Anda dapat menyimpan 4 byte dengan menghapus tanda kurung di sekitar parameter lambda ndan new Random().
Jakob
3

PHP, 30 byte

    while($argn<$n=rand());echo$n;

Jalankan dengan echo <N> | php -Rn '<code>'.

mengambil nomor acak antara 0 dan getrandmax()(2 ** 31-1 pada mesin 64 bit saya);
ulangi sementara itu lebih besar dari input.

Ini mungkin membutuhkan waktu ... AMD C-50 (1 GHz) saya dibutuhkan antara 0,3 dan 130 detik untuk N=15.

Cara yang lebih cepat untuk rata-rata N( 46 byte ):

for(;++$i<$x=1+$argn;)$n+=rand()%$x;echo$n%$x;

atau

for(;++$i<$x=1+$argn;$n%=$x)$n+=rand();echo$n;

mengambil N+1bilangan bulat acak, menjumlahkannya dan mengambil modulo dengannya N+1.
C-50 membutuhkan sekitar. 8 detik untuk 1 juta putaran.

Solusi yang tidak valid untuk 19 byte :

echo rand(0,$argn);
Titus
sumber
3

PowerShell , 35 byte

for(;($a=Random 1gb)-gt"$args"){}$a

Cobalah online!

Metode pengambilan sampel penolakan lainnya. Ini adalah forloop tak terbatas , menetapkan nilai $amenjadi Randombilangan bulat antara 0dan 1gb( = 1073741824 = 2^30), dan terus berulang sepanjang bilangan bulat itu -greater tdari input $args. Setelah loop selesai, kita tinggal memasang $apipeline dan outputnya implisit.

Catatan: Ini akan memakan waktu lama jika inputnya sedikit.

AdmBorkBork
sumber
3

Python 2 , 72 69 byte

-3 bytes berkat xnor (menimpa bawaan idsebagai variabel)

from random import*
n=input()
while id>n:id=randrange(2**30)
print id

Cobalah online!

randrange(2**30)menghasilkan angka didistribusikan semu-seragam (Mersenne Twister 2 19937-1 ) dari kisaran [0,2 30 ) . Karena ndijamin berada di bawah 2 30 ini dapat dengan mudah dipanggil berulang kali hingga tidak lebih besar dari input. Diperlukan waktu yang lama untuk nilai yang sangat rendah n, tetapi biasanya bekerja dalam satu menit bahkan untuk input serendah 50.

Jonathan Allan
sumber
2
Anda dapat menginisialisasi r=''sebagai "tak terbatas". Atau, lebih baik lagi, jangan menginisialisasi rdan gunakan di idmana-mana r.
xnor
2

05AB1E , 11 byte

žIÝ.rDI›_Ϥ

Cobalah online!

Penjelasan

žIÝ          # push the inclusive range [0 ... 2^31]
   .r        # get a random permutation (pythons random.shuffle)
     D       # duplicate this list
      I      # push input
       ›_Ï   # keep only elements from the list not greater than input
          ¤  # take the last one

Karena daftar [0 ... 2147483648]terlalu besar untuk TIO, maka tautannya akan digunakan 1.000.000.

Alternatif (rata-rata) solusi 11 byte yang jauh lebih cepat

[žIÝ.RD¹›_#

Cobalah online

Penjelasan

[             # start loop
 žIÝ          # push the inclusive range [0 ... 2^31]
    .R        # pick a random integer (pythons random.chiose)
      D       # duplicate
       ¹      # push input
        ›_#   # break if random number is not greater than input
              # implicitly output top of stack (the random number)
Emigna
sumber
žJL.R%untuk 6 kecuali saya kehilangan sesuatu yang besar. Tekan 2 ^ 32, daftar dari 0 hingga 2 ^ 32, pilih acak. Input modulo. Benar-benar akan merusak efisiensi yang Anda miliki.
Magic Octopus Urn
@ carusocomputing. Anda akan membutuhkan Idi sana selama 7 byte untuk mendapatkan argumen untuk modulus dalam urutan yang benar (dan mungkin Ýbukan L), tetapi sebaliknya itu tentu saja solusi yang lebih pendek. Saya melihat Dennis melakukan itu dalam jawaban Jelly-nya, tetapi karena ini adalah ide pertama saya, saya menyimpan ini. Karena pendekatan itu berbeda dari ini, Anda dapat mempostingnya sebagai jawaban terpisah.
Emigna
DI‹Ïakan menghindari loop.
Magic Octopus Urn
Juga, apa adanya, ini tidak dijamin akan berakhir; jika saya tidak salah, input dari 0hampir selalu menghasilkan loop yang hampir tak terbatas, membuatnya sulit untuk diakhiri. Meskipun solusinya memungkinkan untuk mengakhiri dalam semua skenario itu tidak dijamin karena keacakan.
Magic Octopus Urn
@carusocomputing: Untuk input yang sangat kecil, versi kedua rata-rata akan membutuhkan waktu yang sangat lama untuk menyelesaikan ya, tetapi diberi cukup waktu.
Emigna
2

Python 2, 89 byte

l=range(2**31)
import random
random.shuffle(l)
n=input()
print filter(lambda x:x<=n,l)[0]

Penjelasan

L=range(2**31)      # Create a list from 0 to 2^31 exclusive. Call it <L>.
import random       # Import the module <random>.
random.shuffle(L)   # Use 'shuffle' function from <random> module,
                    # to shuffle the list <L>.
n=input()           # Take the input -> <n>.

print
    filter(         # Create a new sequence,
    lambda x:x<=n   # where each element is less than or equal to <n>.
    ,L)             # from the list <L>.
    [0]             # Take the first element.

Ini sangat tidak efisien, karena menciptakan 2 ^ 31 bilangan bulat, mengocok dan memfilternya.

Saya tidak melihat gunanya membagikan tautan TIO, di mana ia membuat daftar besar, jadi di sini ada tautan TIO untuk n= 100.

Cobalah online!

Yytsi
sumber
2

Java 8, 84 83 80 71 62 byte

n->{int r;for(;(r=(int)(Math.random()*(1<<30)))>n;);return r;}

-1 byte terima kasih kepada @ OliverGrégoire .
-3 byte terima kasih kepada @Jakob .
-9 byte mengkonversi Java 7 ke Java 8.
-9 byte dengan mengubah java.util.Random().nextInt(1<<30)ke (int)(Math.random()*(1<<30)).

Penjelasan:

Coba di sini.

n->{        // Method with integer parameter and integer return-type
  int r;    //  Result-integer
  for(;(r=(int)(Math.random()*(1<<30)))>n;);
            //  Loop as long as the random integer is larger than the input
            //  (the random integer is in the range of 0 - 1,073,741,824 (2^30))
  return r; //  Return the random integer that is within specified range
}           // End method

CATATAN: Mungkin jelas butuh waktu sangat lama untuk input kecil.

Contoh output:

407594936
Kevin Cruijssen
sumber
2
@ Harun saya mempertanyakan ini juga tetapi melihat poin kedua: "Setiap argumen ketika memanggil fungsi built-in atau library acak harus konstan. Itu mereka harus sepenuhnya independen dari nilai input." Inilah alasan mengapa max int digunakan.
Poke
1
2^30= 1073741824. Anda lebih suka menggunakan -1>>>1(= 2147483647). Tapi ini ada: 1<<30yang persis sama dengan 2^30; dan lebih pendek 1 byte.
Olivier Grégoire
1
Bagaimana dengan int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}?
Jakob
@ Jakob Terima kasih. Saya bahkan mempersingkatnya dengan 18 byte lebih dengan menggunakan Java 8 bukannya 7, dan menggunakan Math.random()bukan java.util.Random().nextInt.
Kevin Cruijssen
2

Python 3, 51 byte

Berikut ini adalah solusi python dengan sumber acak yang tidak lazim.

print(list(set(map(str,range(int(input())+1))))[0])

Cobalah online!

Jadi untuk memecah ini.

int(input())+1

Mendapat nomor input, dan menambahkannya 1.

set(range(...))

Membuat set {0, 1, 2, 3, 4, ... n}untuk semua hasil yang mungkin.

print(list(...)[0])

Mengambil set, mengonversinya menjadi daftar, dan mengambil item pertama.

Ini berfungsi karena dalam Python 3, urutan set()didirikan oleh PYTHONHASHSEED ( tidak dapat diperoleh tetapi ditetapkan pada eksekusi skrip).

Memang, saya menduga bahwa ini adalah distribusi yang seragam, karena hash()nilainya ditentukan secara acak dan saya melihat secara acak memilih nilainya dengan spesifik hash(), alih-alih hanya mengembalikan hash(input())sendiri.

Jika ada yang tahu apakah ini distribusi yang seragam, atau bagaimana saya bisa mengujinya, silakan komentar.

Matt
sumber
1

C #, 57 byte

n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

Fungsi anonim yang mengembalikan bilangan bulat antara 0 dan n inklusif.

Semakin kecil nomor input, semakin lama waktu untuk mengembalikan nilai acak.

Program lengkap:

using System;

class RandomNumber
{
    static void Main()
    {
        Func<int, int> f =
        n=>{int x=n+1;while(x>n)x=new Random().Next();return x;};

        // example
        Console.WriteLine(f(100000));
    }
}
adrianmp
sumber
2
"Argumen apa pun ketika memanggil fungsi built-in atau pustaka acak harus konstan. Itu mereka harus sepenuhnya independen dari nilai input." Argumen untuk Nexttidak statis.
Yytsi
1

Bash + coreutils, 20 byte

Golf

seq 0 $ 1 | shuf | sed 1q

shuf - menghasilkan permutasi acak

Shuf akan menggunakan kode berikut : untuk menghasilkan permutasi:

permutation = randperm_new (randint_source, head_lines, n_lines);

yang berakhir pada randint_genmax

/* Consume random data from *S to generate a random number in the range
0 .. GENMAX.  */

randint
randint_genmax (struct randint_source *s, randint genmax) 
{
      ...

      randread (source, buf, i);

      /* Increase RANDMAX by appending random bytes to RANDNUM and
         UCHAR_MAX to RANDMAX until RANDMAX is no less than
         GENMAX.  This may lose up to CHAR_BIT bits of information
         if shift_right (RANDINT_MAX) < GENMAX, but it is not
         worth the programming hassle of saving these bits since
         GENMAX is rarely that large in practice.  */
      ...
}

yang, pada gilirannya, akan membaca beberapa byte data acak dari sumber tingkat keacakan yang rendah:

/* Consume random data from *S to generate a random buffer BUF of size
   SIZE.  */

void
randread (struct randread_source *s, void *buf, size_t size)
{
  if (s->source)
    readsource (s, buf, size);
  else
    readisaac (&s->buf.isaac, buf, size);
}

yaitu pada level rendah, tidak ada ketergantungan langsung antara nilai shufinput dan data yang dibaca dari sumber keacakan (selain dari menghitung kapasitas buffer byte yang diperlukan).

zeppelin
sumber
6
Bukankah ini memberikan input sebagai argumen ke generator nomor acak Anda?
Martin Ender
Bahkan jika ini tidak valid, kirimkan jawaban bash lain!
@ MartinEnder baik, tidak secara langsung, hanya menggunakan input untuk menentukan batas atas untuk rentang bilangan bulat yang dihasilkan dan jot will arrange for all the values in the range to appear in the output with an equal probability(itu mungkin garis batas, tetapi masih).
zeppelin
2
Jika saya menggali cukup dalam ke generator nomor acak apa pun, saya yakin saya akan menemukan panggilan ke RNG tingkat rendah yang tidak secara langsung menggunakan argumen asli. Inti dari tantangannya adalah untuk mendapatkan distribusi seragam ukuran sewenang-wenang dari distribusi ukuran-tetap, yang masih belum Anda lakukan.
Martin Ender
1

SmileBASIC, 38 byte

INPUT N@L
R=RND(1<<30)ON N<=R GOTO@L?R

Menghasilkan angka acak hingga mendapat nomor yang lebih kecil dari input.

12Me21
sumber
1

Ruby, 23 15 23 32 29 byte

->n{1while n<q=rand(2**30);q}

Bagaimana itu bekerja:

  • 1while [...]; menjalankan pernyataan setidaknya sekali: 1 sebelum whilebertindak sebagai tidak
  • Dapatkan nomor acak di kisaran 0..2 ^ 30-1 ( lebih rendah dari 2 ^ 30 , seperti yang ditentukan)
  • Ulangi jika angkanya lebih tinggi dari parameter input (Dapat memakan waktu ketika n kecil)
GB
sumber
1

Ohm, 26 byte

IΩ
D31º#╬D0[>?D-+∞;,

Penjelasan:

IΩ                 ■Main wire
IΩ                 ■Call wire below

D31º#╬D0[>?D-+∞;,  ■"Real main" wire
D                  ■Duplicate input
 31º#╬D            ■Push random_int in [0..2^31] twice
       0[          ■Push input again
         >?    ;   ■If(random_int > input){
           D-+     ■  remove the random_int
              ∞    ■  recursion
               ;   ■}
                ,  ■Print random_int
Roman Gräf
sumber
Apakah ada penerjemah untuk bahasa ini? Dan bagaimana dengan halaman kode?
ATaco
@ATaco: Penerjemah , Kode-halaman: CP-437
Emigna
1

Golang, 84 78 71 byte

import."math/rand"
func R(n int)int{q:=n+1;for;q>=n;q=Int(){};return q}

Pengambilan sampel penolakan sederhana.

Catatan: karena matematika / rand seed adalah konstanta 1, pemanggil harus seed kecuali hasil yang konstan diinginkan.

Uji: https://play.golang.org/p/FBB4LKXo1r Praktis tidak lagi dapat diuji pada sistem 64-bit, karena itu mengembalikan keacakan 64-bit dan menggunakan pengujian penolakan.

package main

import "fmt"
import "time"

/* solution here *//* end solution */

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
Bersepeda
sumber
1
jika Anda menggunakan import."math/rand"maka Int31tersedia di namespace global dan Anda dapat menghemat 4 byte, juga intdijamin setidaknya 32 bit, menghemat 6 byte lagi
Kristoffer Sall-Storgaard
Gunakan :=sintaks untuk 3 byte lainnya
Kristoffer Sall-Storgaard
Menggunakan int bukan int32 tidak menyimpan byte karena kita perlu membuang hasil Int31 () - 3 * int + () = 11 byte versus 2 * int32 = 10 byte.
Bersepeda
1
Tidak perlu dilemparkan, ada Int()fungsi dalam paket rand, juga, Anda dapat menghapus ruang setelahimport
Kristoffer Sall-Storgaard