Zadanie
Biorąc pod uwagę dodatnią liczbę całkowitą n
mniejszą niż 2^30
określona jako dane wejściowe w dowolny sposób, jaki wybierzesz, twój kod powinien wypisywać losową liczbę całkowitą pomiędzy 0
i n
włącznie. Wygenerowaną liczbę należy losowo wybierać równomiernie . Oznacza to, że każda wartość od 0
do n
musi wystąpić z jednakowym prawdopodobieństwem (patrz Reguły i zastrzeżenia).
Zasady i zastrzeżenia
Twój kod może zakładać, że dowolny generator liczb losowych wbudowany w Twój język lub standardową bibliotekę, który twierdzi, że jest jednolicie losowy, jest w rzeczywistości jednolity. Oznacza to, że nie musisz się martwić o jakość losowego źródła, którego używasz. Jednak,
- Musisz ustalić, że jeśli losowe źródło, którego używasz, jest jednolite, kod poprawnie wypisuje jednolitą losową liczbę całkowitą od
0
don
. - Wszelkie argumenty podczas wywoływania funkcji losowej wbudowanej lub bibliotecznej muszą być stałe. Oznacza to, że muszą być całkowicie niezależne od wartości wejściowej.
- Twój kod może zostać zakończony z prawdopodobieństwem 1, a nie gwarantowany.
Uwagi
randInt(0,n)
nie jest poprawny, ponieważ pobiera dane wejściowe jako argument do funkcji wbudowanej lub biblioteki.rand()%n
będzie nie dać jednolity liczb losowych w ogóle. Jako przykład podany przez betseg, jeśliintmax == 15
in = 10
, wtedy będziesz o wiele bardziej prawdopodobne0-5
niż6-10
.floor(randomfloat()*(n+1))
nie da również ogólnie jednolitej liczby losowej ze względu na skończoną liczbę różnych możliwych wartości zmiennoprzecinkowych od 0 do 1.
code-golf
number
random
probability-theory
całkowicie ludzki
źródło
źródło
rng()
zapewnia0
-100
, jeślin = 75
i funkcja jestrng()%75
, wtedy 0-25 będzie bardziej powszechne ...)Odpowiedzi:
Maszyny x86 z
rdrand
instrukcją, 10 bajtówkod maszynowy
Wejście znajduje się w rejestrze,
rdi
a wyjście wrax
.Jest to zgodne z SYS V AMD64 ABI, więc kod skutecznie implementuje funkcję C.
z 32-bitowymi intami.
Instrukcja
rdrand
została opisana przez firmę IntelW przypadku CSRNG zakłada się, że i tak rozkład jest jednolity, cytując NIST SP 800-90A:
Procedura generuje liczbę losową, a jeśli nie jest ściśle większa niż wartość wejściowa, jest zwracana.
W przeciwnym razie proces jest powtarzany.
Ponieważ
eax
jest 32-bitowy,rdrand
zwraca liczbę z zakresu od 0 do 2 32 -1, więc dla każdego n w [0, 2 32 -1] liczba oczekiwanych iteracji wynosi 2 32 / (n + 1), która jest zdefiniowana dla wszystkich n w [0, 2 30 ).źródło
jnc
za?rdrand
ustawia, czyCF
zwracane dane są prawidłowe. Dane mogą być nieprawidłowe, ponieważ zbyt wiele żądań opróżniło pulę entropii. Zobacz ręczny wpis dla rdrand i tego .Galaretka ,
76 bajtówDzięki @JonathanAllan za grę w golfa na 1 bajcie!
Nie można uruchomić na TIO, ponieważ (16!)! to ogromna liczba.
Jak to działa
źródło
Mathematica, 29 bajtów
Na podstawie odpowiedzi Jelnisa na żelki .
Nie poleciłbym, żeby to uruchomić.
2e9!
to całkiem duża liczba ...Najkrótsze okazuje się wygenerowanie ogromnej liczby, która jest podzielna przez wszystkie możliwe dane wejściowe, i odwzorowanie wyniku na wymagany zakres za pomocą prostego modulo.
Próbka odrzucenia, 34 bajty
Moje stare podejście, które doprowadziło do nieco ciekawszego kodu:
Podstawowe pobieranie próbek odrzucenia. Inicjujemy wyjście do 13! (która jest większa niż maksymalna wartość wejściowa 2 30 ), a następnie kilkakrotnie zastępuj ją losową liczbą całkowitą od 0 do 13! dopóki wartość jest większa niż wartość wejściowa.
źródło
Brachylog , 9 bajtów
Wypróbuj online!
Wykorzystuje to
13!
jak w odpowiedzi Martina Endera (13ḟ
jest o jeden bajt mniej niż2^₃₀
).ṙ
jest implementowany przy użyciurandom_between/3
, który podczas kopania źródła wykorzystuje zastosowania, zrandom_float/0
którymi jest powiązany,random/1
który wykorzystuje jednolity dla naszych celów algorytm Mersenne Twister.Wyjaśnienie
źródło
Prolog (SWI) , 38 bajtów
Działa przez próbkowanie odrzucenia.
Wygeneruj liczbę losową z przedziału od 0 do 2 ^ 31-1 = 2147483647, dopóki nie zostanie znaleziona wartość mniejsza lub równa wartości wejściowej.
Czuję, że powinienem móc użyć cięcia zamiast innych, ale nie widzę, jak to zrobić.
źródło
repeat
, ale kończy się to o 3 bajty dłużej… Nie jestem pewien, czy istnieje krótszy sposób na uzyskanie nieskończonej liczby punktów wyboru niż powtórzenie.,!.
Pamiętałem o użyciu czegoś takiego jak wymuszenie powrotu, ale albo źle pamiętam, albo nie dotyczy to tego rozwiązania.Labirynt , 63 bajty
(Dzięki @MartinEnder za pomoc w ciężkim golfie tutaj.)
Labirynt jest językiem 2D, a jego jedynym źródłem losowości jest sytuacja:
Załóż, że wskaźnik instrukcji znajduje się na
x
i przesuwa się w dół. Następnie ląduje na<
, który, jeśli górna część stosu ma wartość 0 (co zawsze ma miejsce w przypadku powyższego programu), przesuwa bieżący wiersz w lewo o 1:Wskaźnik instrukcji
<
przesuwa się teraz w dół. Na skrzyżowaniu Labirynt skręca na podstawie stosu - ujemny oznacza skręt w lewo, dodatni - skręt w prawo, a zero - ruch do przodu. Jeśli w tym momencie górna część stosu nadal wynosi zero, nie możemy poruszać się do przodu ani do tyłu, ponieważ nie ma ścieżki, więc Labirynt losowo losowo skręca w lewo lub w prawo z jednakowym prawdopodobieństwem.Zasadniczo powyższy program używa funkcji losowości do generowania liczb 100-bitowych (100 określonych
#00
tutaj) i kontynuuje zapętlanie, aż wygeneruje liczbę<= n
.Do testowania prawdopodobnie pomoże
#0"
zamiast tego użyć liczb 10-bitowych, ponieważ"
jest to ścieżka , na którą nie można się oprzeć. Wypróbuj online!Szorstkie wyjaśnienie:
źródło
Python, 61 bajtów
Edycja: Zaktualizowano, aby uniknąć niedozwolonej formy
Edycja2: Zapisano 2 bajty, dzięki @ JonathanAllan
Edycja3: Zapłacono 2 bajty za w pełni funkcjonalne rozwiązanie - jeszcze raz dziękuję @JonathanAllan
Edycja4: Usunięto
f=
, zapisując 2 bajtyEdycja5: Zaoszczędzono jeszcze 1 bajt dzięki @ JonathanAllan
Edycja6: Zaoszczędź 2 kolejne bajty dzięki @ JonathanAllan
Do tej pory wina git wskazywałaby na mnie za złe rzeczy, a Jonathan Allan na rzeczy, które pomagają.
Edycja7: Kiedy pada deszcz, leje - kolejne 2 bajty
Edycja8: I kolejne 2 bajty
źródło
n
, ale możesz zapisać dwa bajty, gdy naprawisz to za pomocąfrom random import*
i upuszczającr.
....*(-~n*1.0/2**30))
zamiast tego...*((n+1)*1.0/2**30))
randrange
Wydaje się , że akceptuje liczbę zmiennoprzecinkową, więclambda n,x=2.**30:int(randrange(x)*-~n/x)
zapisuje kolejne dwa [edytuj ...] cztery!Python 2 , 61 bajtów
Pseudo-losowo wybiera liczby całkowite pomiędzy 0 i k dla wszystkich wartości K między 0 i 2, 31 - 2 , a następnie wykonuje się całkowitą odpowiadającą k = N .
źródło
Partia, 64 bajty
%random%
daje tylko 15 bitów losowości, więc muszę połączyć dwie losowe liczby. Pętle, aż wartość losowa znajdzie się w pożądanym zakresie, więc powoli dla niskiejn
; 98 bajtów dla szybszej wersji:źródło
n
?call
, wywołanie skryptu wsadowego spowoduje zakończenie bieżącego skryptu.MATL , 12 bajtów
Dzięki @AdmBorkBork i @Suever za informację, jak wyłączyć pamięć podręczną TIO.
Wypróbuj online! .
Używa to metody odrzucania : generuje losową liczbę całkowitą od
0
do2^30-1
i powtarza, gdy przekroczy ona wartość wejściowąn
. Gwarantuje to, że zakończy się z prawdopodobieństwem1
, ale średnia liczba iteracji jest2^30/n
, a więc zajmuje bardzo długo, abyn
znacznie mniejsza niż2^30
.źródło
JavaScript (ES6),
5554 bajtówGeneruje liczby całkowite z zakresu [0 ... 2 k - 1] , gdzie k jest najmniejszą liczbą całkowitą taką, że 2 k jest większe niż n . Powtarzane, dopóki wynik nie spadnie do [0 ... n] .
Czemu?
Jest to oparte na następujących założeniach:
Wewnętrznie pseudolosowe wartości całkowite generowane przez silnik JS do zasilania
Math.random()
są jednolite w dowolnym przedziale [0 ... 2 k -1] (z k <32 ).Po pomnożeniu przez dokładną potęgę 2, wartości zmiennoprzecinkowe IEEE 754 zwracane przez
Math.random()
są nadal jednolite w takich przedziałach.Jeśli ktoś może potwierdzić lub obalić te hipotezy, daj mi znać w komentarzach.
Próbny
Generuje 1 milion wartości w [0 ... 2] i wyświetla statystyki wyników.
Pokaż fragment kodu
źródło
Bash (+ coreutils), 44 bajty
Rozwiązanie oparte na / dev / urandom
Odczyta 32-bitowe liczby całkowite bez znaku
/dev/urandom
i odfiltruje je,awk
aż znajdzie jedną w danym zakresie, a następniesed q
przerwie potok.źródło
Haskell, 70 bajtów
Niezbyt wydajny algorytm, ale działa. Generuje nieskończoną listę liczb całkowitych (lub liczb zmiennoprzecinkowych w razie potrzeby, ze względu na system typów Haskella) ograniczonych przez [0,2 ^ 30] i przyjmuje pierwszą mniejszą lub równą n. W przypadku małych n może to zająć dużo czasu. Liczby losowe powinny być równomiernie rozmieszczone, jak określono w dokumentacji dla randomR, więc wszystkie liczby w przedziale [0,2 ^ 30] powinny mieć takie samo prawdopodobieństwo (1 / (2 ^ 30 + 1)), dlatego wszystkie liczby w [ 0, n] mają takie samo prawdopodobieństwo.
Alternatywna wersja:
Ta wersja jest okropna, ale oszczędza cały bajt.
randoms
używa dowolnego zakresu określonego przez typ do wygenerowania nieskończonej listy liczb. Może to obejmować negatywy, dlatego musimy zmapować je,abs
aby wymusić ich dodatnie (lub zero). Jest to bardzo wolne dla wszystkich wartości n, które nie są absurdalnie duże. EDYCJA : Zorientowałem się później, że ta wersja nie jest równomiernie rozłożona, ponieważ prawdopodobieństwo uzyskania 0 jest gorsze niż w przypadku innych liczb z powodu użyciaabs
. Aby wyprodukować pewną liczbęm
generator mógłby produkowaćm
albo-m
ale w przypadku 0 0 tylko sama będzie działać, dlatego jego prawdopodobieństwo jest połowa z pozostałych numerów.źródło
Galaretka , 9 bajtów
Wypróbuj online! - powyższy kod nie będzie działał na TIO, ponieważ zakres rozmiaru 16! muszą zostać zbudowane jako pierwsze (nie wspominając o tym, że należy je przetasować, a następnie przefiltrować!), więc jest to ta sama rzecz na znacznie mniejszą skalę, powtarzane 30 razy dla danych wejściowych 3 z granicą 10.
W jaki sposób?
Uwaga: byłby ponad tysiąc razy bardziej wydajny dla tej samej liczby bajtów, gdyby
ȷ⁵
zrobił to, czego naiwnie oczekiwałby i zwróciłby dziesięć do dziesięciu, ale tak nie jest, ponieważ⁵
nie jest on oceniany jako dosłowna dziesiątka do użycia według liczby literalnej,ȷ...
ale raczej dwa oddzielne literały są analizowane,ȷ
przy czym domyślny wykładnik trzech daje tysiąc, a⁵
dziesięćźródło
JDK 9 na jshell,
7559 bajtówStosowanie
OptionalInt
. Reguły nie określają, że typ zwracany musi być prymitywny i uważam, żeOptionalInt
jest to poprawna reprezentacja wyniku.źródło
Optional
jest akceptowana. Potwierdziłbym z plakatem, gdybym był tobą. Nie trzeba też liczyć całego zadania; wystarczy wyrażenie lambda.n
inew Random()
.PHP, 30 bajtów
Uruchom z
echo <N> | php -Rn '<code>'
.wybiera losową liczbę od 0 do
getrandmax()
(2 ** 31-1 na mojej 64-bitowej maszynie);powtarza się, gdy jest on większy niż wejście.
To może trochę potrwać ... mój AMD C-50 (1 GHz) potrzebne między 0,3 a 130 sekund
N=15
.Szybszy sposób na średnią
N
( 46 bajtów ):lub
bierze
N+1
losowe liczby całkowite, sumuje je i bierze moduloN+1
.C-50 potrzebuje ok. 8 sekund na 1 milion przebiegów.
Niepoprawne rozwiązanie dla 19 bajtów :
źródło
PowerShell , 35 bajtów
Wypróbuj online!
Kolejna metoda próbkowania odrzucenia. Jest nieskończona
for
pętli ustalania wartości$a
do byćRandom
liczbą całkowitą od0
i1gb
(= 1073741824 = 2^30
) i zawraca w pętli tak długo, jak całkowita jest-g
reatert
Han wejściowego$args
. Po zakończeniu pętli po prostu instalujemy$a
potok, a dane wyjściowe są niejawne.Uwaga: Zajmie to dużo czasu, jeśli wprowadzona liczba będzie niewielka.
źródło
Python 2 ,
7269 bajtów-3 bajty dzięki xnor (przesłania
id
wbudowaną zmienną)Wypróbuj online!
randrange(2**30)
produkuje pseudo-równomiernie rozłożoną liczbę (Mersenne Twister 2 19937-1 ) z zakresu [0,2 30 ) . Ponieważn
gwarantowana jest wartość poniżej 2 30, można to po prostu wywoływać wielokrotnie, dopóki nie będzie większa niż wartość wejściowa. Bardzo niskie wartości zajmie długo oczekiwany czasn
, ale zwykle działa w ciągu minuty, nawet przy wejściach tak niskich jak 50.źródło
r=''
jako „nieskończoność”. Lub, jeszcze lepiej, nie inicjujr
i zamiast tego używajid
wszędzie dor
.Perl 6 , 29 bajtów
Zainspirowany rozwiązaniem Mathematica Martina Endera .
Generuje leniwą nieskończoną sekwencję losowych liczb całkowitych od 0 do 2 ^ 30-1 i przyjmuje pierwszą, która jest między 0 a wejściem.
Wypróbuj online!
źródło
05AB1E , 11 bajtów
Wypróbuj online!
Wyjaśnienie
Ponieważ lista
[0 ... 2147483648]
jest zbyt duża dla TIO, link używa1.000.000
zamiast tego.Alternatywne (średnio) znacznie szybsze 11 bajtowe rozwiązanie
Wypróbuj online
Wyjaśnienie
źródło
žJL.R%
za 6, chyba że brakuje mi czegoś wielkiego. Naciśnij 2 ^ 32, lista od 0 do 2 ^ 32, losowy wybór. Wejście modulo. Absolutnie pogorszy Twoją wydajność.I
7 bajtów, aby uzyskać argumenty za modułem we właściwej kolejności (a możeÝ
zamiastL
), ale w przeciwnym razie jest to z pewnością krótsze rozwiązanie. Widziałem, jak Dennis robi to w odpowiedzi na Jelly, ale ponieważ był to mój pierwszy pomysł, zachowałem to. Ponieważ to podejście różni się od tego, możesz opublikować je jako osobną odpowiedź.DI‹Ï
uniknie pętli.0
prawie zawsze skutkuje prawie nieskończoną pętlą, co utrudnia zakończenie. Chociaż rozwiązanie to umożliwia zakończenie we wszystkich scenariuszach, nie jest gwarantowane z powodu losowości.Python 2, 89 bajtów
Wyjaśnienie
Jest to bardzo nieefektywne, ponieważ tworzy 2 ^ 31 liczb całkowitych, tasuje je i filtruje.
Nie widzę sensu w udostępnianiu linku TIO, w którym tworzy on tak duże listy, więc tutaj jest link TIO dla
n
= 100.Wypróbuj online!
źródło
Java 8,
8483807162 bajtów-1 bajt dzięki @ OliverGrégoire .
-3 bajty dzięki @Jakob .
-9 bajtów, konwersja Java 7 na Javę 8.
-9 bajtów przez zmianę
java.util.Random().nextInt(1<<30)
na(int)(Math.random()*(1<<30))
.Wyjaśnienie:
Wypróbuj tutaj.
UWAGA: W przypadku małych nakładów może to oczywiście potrwać bardzo długo.
Przykładowe dane wyjściowe:
źródło
2^30
=1073741824
. Wolałeś używać-1>>>1
(=2147483647
). Ale to istnieje:1<<30
co jest dokładnie równe2^30
; i jest o 1 bajt krótszy.int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}
?Math.random()
zamiastjava.util.Random().nextInt
.Python 3, 51 bajtów
Oto rozwiązanie python z niekonwencjonalnym losowym źródłem.
Wypróbuj online!
Aby to rozbić.
Pobiera numer wejściowy i dodaje
1
go.Tworzy zestaw
{0, 1, 2, 3, 4, ... n}
dla wszystkich możliwych wyników.Bierze zestaw, konwertuje go na listę i chwyta pierwszy przedmiot.
Działa to, ponieważ w Pythonie 3 kolejność
set()
jest ustalana przez PYTHONHASHSEED ( nie można uzyskać, ale jest ustalana podczas wykonywania skryptu).Wprawdzie zgaduję, że jest to rozkład równomierny, ponieważ
hash()
wartość jest losowo przypisywana i patrzę na losowe wybieranie wartości z konkretnymhash()
, a nie tylko zwracaniemhash(input())
samej.Jeśli ktoś wie, czy jest to jednolity rozkład lub jak mógłbym to przetestować, proszę o komentarz.
źródło
C #, 57 bajtów
Anonimowa funkcja, która zwraca liczbę całkowitą od 0 do n włącznie.
Im mniejsza liczba wejściowa, tym dłuższy jest czas na zwrócenie losowej wartości.
Pełny program:
źródło
Next
nie jest statyczny.Bash + coreutils, 20 bajtów
Grał w golfa
seq 0 $ 1 | shuf | sed 1q
Shuf użyje następującego kodu : do generowania permutacji:
co kończy się w
randint_genmax
który z kolei odczyta kilka bajtów losowych danych z niskiego poziomu źródła losowości:
tj. na niskim poziomie nie ma bezpośredniej zależności między
shuf
wartością wejściową a danymi odczytanymi ze źródła losowości (oprócz obliczenia wymaganej pojemności bufora bajtów).źródło
jot will arrange for all the values in the range to appear in the output with an equal probability
(to prawdopodobnie granica, ale nadal).SmileBASIC, 38 bajtów
Generuje liczby losowe, aż otrzyma liczbę mniejszą niż wartość wejściowa.
źródło
Rubin,
23 15 23 3229 bajtówJak to działa:
1while [...];
wykonuje instrukcję co najmniej raz:1
zanimwhile
działa jak nopźródło
Ohm, 26 bajtów
Wyjaśnienie:
źródło
Udać się,
6361 bajtówUżyj tego w ten sposób:
Przetestuj na żywo na placu zabaw
źródło
Golang,
847871 bajtówProste próbkowanie odrzucenia.
Uwaga: ponieważ ziarno matematyczne / rand jest stałą 1, dzwoniący musi wysiać nasiona, chyba że pożądany jest stały wynik.
Test: https://play.golang.org/p/FBB4LKXo1rNie jest już praktycznie testowany w systemie 64-bitowym, ponieważ zwraca 64-bitową losowość i używa testu odrzucania.źródło
import."math/rand"
toInt31
jest dostępny w globalnej przestrzeni nazw i możesz zapisać 4 bajty,int
gwarantuje również co najmniej 32 bity, oszczędzając ci kolejne 6 bajtów:=
składni dla kolejnych 3 bajtówInt()
w pakiecie rand znajduje się funkcja, można też usunąć miejsce późniejimport