Wybierz losową liczbę od 0 do n, używając stałego źródła losowości

26

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą nmniejszą niż 2^30określona jako dane wejściowe w dowolny sposób, jaki wybierzesz, twój kod powinien wypisywać losową liczbę całkowitą pomiędzy 0i nwłącznie. Wygenerowaną liczbę należy losowo wybierać równomiernie . Oznacza to, że każda wartość od 0do nmusi 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 0do n.
  • 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()%nbędzie nie dać jednolity liczb losowych w ogóle. Jako przykład podany przez betseg, jeśli intmax == 15i n = 10, wtedy będziesz o wiele bardziej prawdopodobne 0-5niż 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.
całkowicie ludzki
źródło
Jak zamierzasz potwierdzić, że wyjście jest jednolicie losowe? Może się zdarzyć, że dany język / biblioteka wygeneruje jednolicie losowe liczby, ale manipulacja może spowodować niejednolity wynik. (np. rng()zapewnia 0- 100, jeśli n = 75i funkcja jest rng()%75, wtedy 0-25 będzie bardziej powszechne ...)
Baldrickk
1
@Baldrickk Według mądrości tłumów :) Możemy tylko czytać kod i myśleć o nim.
Smutny wniosek zadawania najprostszego możliwego pytania teorii prawdopodobieństwa: losowość i prawdopodobieństwo są bardzo słabo zrozumiane. :( (Widocznie czytanie zasad jest trudne.)
Martin Ender
To przychodzi mi na myśl: Random Number
BgrWorker
Dlaczego zaakceptowałeś odpowiedź x86, gdy są trzy krótsze?
Dennis

Odpowiedzi:

25

Maszyny x86 z rdrandinstrukcją, 10 bajtów

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

kod maszynowy

0FC7F0 73FB 39F8 77F7 C3

Wejście znajduje się w rejestrze, rdia wyjście w rax.
Jest to zgodne z SYS V AMD64 ABI, więc kod skutecznie implementuje funkcję C.

unsigned int foo(unsigned int max); 

z 32-bitowymi intami.

Instrukcja rdrandzostała opisana przez firmę Intel

RDRANDzwraca liczby losowe dostarczane przez kryptograficznie bezpieczny, deterministyczny generator bitów losowych DRBG. DRBG został zaprojektowany w celu spełnienia normy NIST SP 800-90A .

W przypadku CSRNG zakłada się, że i tak rozkład jest jednolity, cytując NIST SP 800-90A:

Liczba losowa jest instancją bezstronnej zmiennej losowej, to znaczy wynikiem generowanym przez równomiernie rozłożony losowy proces.


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ż eaxjest 32-bitowy, rdrandzwraca 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 ).

Margaret Bloom
źródło
Genialnie niski poziom. Dziękuję Ci.
Co to jest jncza?
l4m2
@ l4m2 rdrandustawia, czy CFzwracane 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 .
Margaret Bloom
20

Galaretka , 7 6 bajtów

⁴!!X%‘

Dzięki @JonathanAllan za grę w golfa na 1 bajcie!

Nie można uruchomić na TIO, ponieważ (16!)! to ogromna liczba.

Jak to działa

⁴!!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
źródło
To jest poprawiona wersja mojej skasowanej odpowiedzi, ten sam pomysł. Chociaż miałem niepotrzebne potęgowanie.
orlp
Przepraszam, nie patrzyłem na to przed opublikowaniem.
Dennis
Och, to nie ma znaczenia, i tak nie planowałem go naprawić. Jestem zbyt niewygodny z Jelly, żeby naprawdę się z tym bawić.
orlp
1
„Sir, nie wiem, dlaczego jesteś wściekły. Algorytm to ciągły czas. To dobrze, prawda? Dlaczego ochrona i HR są za drzwiami?”
corsiKa
1
Zgoda. Różnica między liczbą 8-cyfrową a liczbą 417 kwintillionów: p
Jonathan Allan
11

Mathematica, 29 bajtów

Na podstawie odpowiedzi Jelnisa ​​na żelki .

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

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:

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

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.

Martin Ender
źródło
1
Masz na myśli „mniejszy lub równy wkładowi”?
1
@Lembik Nie. Chcemy zregenerować wartość, o ile nie mieści się ona w pożądanym zakresie.
Martin Ender
Rozumiem. Z jakiegoś powodu myślałem, że wielokrotnie próbowaliśmy z pożądanego zakresu. Dzięki.
1
Przypomnij mi, żebym następnym razem
9

Brachylog , 9 bajtów

≥.∧13ḟṙ|↰

Wypróbuj online!

Wykorzystuje to 13!jak w odpowiedzi Martina Endera ( 13ḟjest o jeden bajt mniej niż 2^₃₀).

jest implementowany przy użyciu random_between/3, który podczas kopania źródła wykorzystuje zastosowania, z random_float/0którymi jest powiązany, random/1który wykorzystuje jednolity dla naszych celów algorytm Mersenne Twister.

Wyjaśnienie

≥.           Input ≥ Output
  ∧          And
   13ḟṙ      Output = rand(0, 13!)
       |     Else
        ↰    Call recursively with the same input
Fatalizować
źródło
7

Prolog (SWI) , 38 bajtów

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

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ć.

Emigna
źródło
1
Można uniknąć użycia innych 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.
Fatalize
@Fatalize: Tak, próbowałem również powtórzyć. ,!.Pamiętałem o użyciu czegoś takiego jak wymuszenie powrotu, ale albo źle pamiętam, albo nie dotyczy to tego rozwiązania.
Emigna
7

Labirynt , 63 bajty

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

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

   x
  "<)
 " "
 " "

Załóż, że wskaźnik instrukcji znajduje się na xi 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 #00tutaj) 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:

 ?            <--- ? 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
źródło
7

Python, 61 bajtów

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

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 bajty

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

iwaseatenbyagrue
źródło
1
To nigdy nie zostanie wyprowadzone n, ale możesz zapisać dwa bajty, gdy naprawisz to za pomocą from random import*i upuszczając r..
Jonathan Allan
1
Tak, możesz użyć „operatora kijanki”, aby uniknąć niepotrzebnych nawiasów, więc ...*(-~n*1.0/2**30))zamiast tego...*((n+1)*1.0/2**30))
Jonathan Allan
1
Naprawdę? Słodkie! Czy od dawna masz pretensje do liczby 70?
Wielkie
1
randrangeWydaje się , że akceptuje liczbę zmiennoprzecinkową, więc lambda n,x=2.**30:int(randrange(x)*-~n/x)zapisuje kolejne dwa [edytuj ...] cztery!
Jonathan Allan
1
^ jeszcze dwa tam z usunięciem nawiasów. Po prostu pokazuje, że mnożenie było właściwą drogą!
Jonathan Allan
6

Python 2 , 61 bajtów

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

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 .

Dennis
źródło
5

Partia, 64 bajty

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

%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 niskiej n; 98 bajtów dla szybszej wersji:

@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
źródło
Kod może być powolny, ale twoja odpowiedź była szybka!
3
@Lembik Miałem gotową odpowiedź na usunięte pytanie ...
Neil
Czy to nie będzie echo żądanej liczby, a potem wszystkich innych liczb, które okazały się większe niż n?
Erik the Outgolfer
@EriktheOutgolfer No; chyba że użyjesz call, wywołanie skryptu wsadowego spowoduje zakończenie bieżącego skryptu.
Neil
5

MATL , 12 bajtów

Dzięki @AdmBorkBork i @Suever za informację, jak wyłączyć pamięć podręczną TIO.

`30WYrqG>}2M

Wypróbuj online! .

Używa to metody odrzucania : generuje losową liczbę całkowitą od 0do 2^30-1i powtarza, gdy przekroczy ona wartość wejściową n. Gwarantuje to, że zakończy się z prawdopodobieństwem 1, ale średnia liczba iteracji jest 2^30/n, a więc zajmuje bardzo długo, aby nznacznie mniejsza niż 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
źródło
4

JavaScript (ES6), 55 54 bajtów

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

Generuje 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.

Arnauld
źródło
Math.floor (Math.random () * (n + 1)) daje mi nie mniej równomiernie rozłożone wyniki, więc fajnie byłoby sprawdzić, czy istnieje jakikolwiek realistyczny N <2 ^ 30, który wytworzy jakiekolwiek anomalie rozkładu w ogóle.
zeppelin
1
@ zeppelin potrzebujesz dużo zbyt wielu próbnych testów, aby wskazać jakiekolwiek anomalie, ponieważ losowa liczba zmiennoprzecinkowa w tym zakresie będzie miała jedną z 2 ^ 53 wartości, które zostaną rozłożone możliwie równomiernie na wyniki 2 ^ 30. Zatem nawet w przypadku dużych liczb w tym zakresie błąd będzie wynosił około 1 na 2 ^ 23, co oznacza, że ​​będziesz potrzebować absurdalnej liczby prób. Prawdopodobnie będziesz potrzebował kilku rzędów wielkości więcej niż liczba próbek początkowych (2 ^ 53). Niemniej jednak nie może być idealnie jednolity, jeśli mnożnik nie dzieli równomiernie liczby próbek, dlatego Arnauld używa potęgi dwóch.
Martin Ender
4

Bash (+ coreutils), 44 bajty

Rozwiązanie oparte na / dev / urandom

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

Odczyta 32-bitowe liczby całkowite bez znaku /dev/urandomi odfiltruje je, awkaż znajdzie jedną w danym zakresie, a następnie sed qprzerwie potok.

zepelin
źródło
Brawo na bash :)
4

Haskell, 70 bajtów

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

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:

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

Ta wersja jest okropna, ale oszczędza cały bajt. randomsużywa dowolnego zakresu określonego przez typ do wygenerowania nieskończonej listy liczb. Może to obejmować negatywy, dlatego musimy zmapować je, absaby 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życia abs. Aby wyprodukować pewną liczbę mgenerator mógłby produkować malbo -male w przypadku 0 0 tylko sama będzie działać, dlatego jego prawdopodobieństwo jest połowa z pozostałych numerów.

użytkownik1472751
źródło
Brawo dla Haskella (też)!
4

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?

⁴!Ẋ’>Ðḟ⁸Ṫ - 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.

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ęć

Jonathan Allan
źródło
Huh, to 9 znaków, ale 22 bajty
Kristoffer Sall-Storgaard
@ KristofferSall-Storgaard Każdy znak jest jednym z 256 bajtów na stronie kodowej Jelly. Zapomniałem, że słowo bajty to link, jak zwykle.
Jonathan Allan
1
rok, sprawdziłem to i dowiedziałem się tego samego
Kristoffer Sall-Storgaard
4

JDK 9 na jshell, 75 59 bajtów

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

Stosowanie

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 bajtów: Dzięki Jakob!
  • Zakłada się, że uważamy jshell za prawidłowe środowisko wykonawcze.
  • Sam jshell, jako środowisko wykonawcze, nie wymaga jawnego importu dla bibliotek podstawowych i nie wymaga średników.
  • Zwraca an OptionalInt. Reguły nie określają, że typ zwracany musi być prymitywny i uważam, że OptionalIntjest to poprawna reprezentacja wyniku.
Pete Terlep
źródło
1
Dzięki @ kevin-cruijssen za inspirację. Mój pierwszy golf golfowy!
Pete Terlep
To, czy akceptowana jest ramka, różni się od tego, czy Optionaljest akceptowana. Potwierdziłbym z plakatem, gdybym był tobą. Nie trzeba też liczyć całego zadania; wystarczy wyrażenie lambda.
Jakob
1
Możesz zapisać 4 bajty, usuwając nawiasy wokół parametru lambda ni new Random().
Jakob
3

PHP, 30 bajtów

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

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

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

lub

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

bierze N+1losowe liczby całkowite, sumuje je i bierze modulo N+1.
C-50 potrzebuje ok. 8 sekund na 1 milion przebiegów.

Niepoprawne rozwiązanie dla 19 bajtów :

echo rand(0,$argn);
Tytus
źródło
3

PowerShell , 35 bajtów

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

Wypróbuj online!

Kolejna metoda próbkowania odrzucenia. Jest nieskończona forpętli ustalania wartości $ado być Randomliczbą całkowitą od 0i 1gb( = 1073741824 = 2^30) i zawraca w pętli tak długo, jak całkowita jest -greater tHan wejściowego $args. Po zakończeniu pętli po prostu instalujemy $apotok, a dane wyjściowe są niejawne.

Uwaga: Zajmie to dużo czasu, jeśli wprowadzona liczba będzie niewielka.

AdmBorkBork
źródło
3

Python 2 , 72 69 bajtów

-3 bajty dzięki xnor (przesłania idwbudowaną zmienną)

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

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ż ngwarantowana 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 czas n, ale zwykle działa w ciągu minuty, nawet przy wejściach tak niskich jak 50.

Jonathan Allan
źródło
2
Możesz zainicjować r=''jako „nieskończoność”. Lub, jeszcze lepiej, nie inicjuj ri zamiast tego używaj idwszędzie do r.
xnor
2

05AB1E , 11 bajtów

žIÝ.rDI›_Ϥ

Wypróbuj online!

Wyjaśnienie

ž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

Ponieważ lista [0 ... 2147483648]jest zbyt duża dla TIO, link używa 1.000.000zamiast tego.

Alternatywne (średnio) znacznie szybsze 11 bajtowe rozwiązanie

[žIÝ.RD¹›_#

Wypróbuj online

Wyjaśnienie

[             # 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
ź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ść.
Magic Octopus Urn
@ carusocomputing. Potrzebujesz I7 bajtów, aby uzyskać argumenty za modułem we właściwej kolejności (a może Ýzamiast L), 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ź.
Emigna
DI‹Ïuniknie pętli.
Magic Octopus Urn
Ponadto, w obecnej postaci, nie gwarantuje się zakończenia; jeśli się nie mylę, wejście 0prawie 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.
Magic Octopus Urn
@carusocomputing: W przypadku bardzo małego wkładu druga wersja zajęłaby średnio bardzo dużo czasu tak, ale biorąc pod uwagę wystarczającą ilość czasu.
Emigna
2

Python 2, 89 bajtów

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

Wyjaśnienie

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.

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!

Yytsi
źródło
2

Java 8, 84 83 80 71 62 bajtów

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

-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.

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

UWAGA: W przypadku małych nakładów może to oczywiście potrwać bardzo długo.

Przykładowe dane wyjściowe:

407594936
Kevin Cruijssen
źródło
2
@Aaron Również to zakwestionowałem, ale widzę drugi punkt: „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”. To jest powód, dla którego użyto max int.
Poke
1
2^30= 1073741824. Wolałeś używać -1>>>1(= 2147483647). Ale to istnieje: 1<<30co jest dokładnie równe 2^30; i jest o 1 bajt krótszy.
Olivier Grégoire
1
Jak o int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}?
Jakob
@Jakob Thanks. Skróciłem go nawet o 18 bajtów, używając Java 8 zamiast 7 i używając Math.random()zamiast java.util.Random().nextInt.
Kevin Cruijssen
2

Python 3, 51 bajtów

Oto rozwiązanie python z niekonwencjonalnym losowym źródłem.

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

Wypróbuj online!

Aby to rozbić.

int(input())+1

Pobiera numer wejściowy i dodaje 1go.

set(range(...))

Tworzy zestaw {0, 1, 2, 3, 4, ... n}dla wszystkich możliwych wyników.

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

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 konkretnym hash(), a nie tylko zwracaniem hash(input())samej.

Jeśli ktoś wie, czy jest to jednolity rozkład lub jak mógłbym to przetestować, proszę o komentarz.

The Matt
źródło
1

C #, 57 bajtów

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

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:

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
źródło
2
„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.” Argument do Nextnie jest statyczny.
Yytsi
1

Bash + coreutils, 20 bajtów

Grał w golfa

seq 0 $ 1 | shuf | sed 1q

shuf - generuj losowe permutacje

Shuf użyje następującego kodu : do generowania permutacji:

permutation = randperm_new (randint_source, head_lines, n_lines);

co kończy się w 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.  */
      ...
}

który z kolei odczyta kilka bajtów losowych danych z niskiego poziomu źródła losowości:

/* 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);
}

tj. na niskim poziomie nie ma bezpośredniej zależności między shufwartością wejściową a danymi odczytanymi ze źródła losowości (oprócz obliczenia wymaganej pojemności bufora bajtów).

zepelin
źródło
6
Czy to nie daje danych wejściowych jako argumentu do generatora liczb losowych?
Martin Ender
Nawet jeśli nie jest to poprawne, prześlij kolejną odpowiedź bash!
@MartinEnder dobrze, nie bezpośrednio, po prostu używa danych wejściowych do zdefiniowania górnego limitu dla generowanego zakresu liczb całkowitych i jot will arrange for all the values in the range to appear in the output with an equal probability(to prawdopodobnie granica, ale nadal).
zeppelin
2
Jeśli zagłębię się wystarczająco głęboko w dowolny generator liczb losowych, jestem pewien, że znajdę wywołanie do RNG niższego poziomu, który nie używa bezpośrednio oryginalnego argumentu. Celem wyzwania jest uzyskanie jednolitego rozkładu o dowolnym rozmiarze z rozkładu o stałej wielkości, czego nadal nie robisz.
Martin Ender
1

SmileBASIC, 38 bajtów

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

Generuje liczby losowe, aż otrzyma liczbę mniejszą niż wartość wejściowa.

12Me21
źródło
1

Rubin, 23 15 23 32 29 bajtów

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

Jak to działa:

  • 1while [...];wykonuje instrukcję co najmniej raz: 1zanim whiledziała jak nop
  • Uzyskaj losową liczbę z zakresu 0..2 ^ 30-1 ( mniejszą niż 2 ^ 30 , jak określono)
  • Powtórz, jeśli liczba jest wyższa niż parametr wejściowy (może zająć trochę czasu, gdy n jest małe)
GB
źródło
1

Ohm, 26 bajtów

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

Wyjaśnienie:

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
źródło
Czy istnieje tłumacz dla tego języka? A co ze stroną kodową?
ATaco
@ATaco: Tłumacz , strona kodowa: CP-437
Emigna
1

Golang, 84 78 71 bajtów

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

Proste 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/FBB4LKXo1r Nie jest już praktycznie testowany w systemie 64-bitowym, ponieważ zwraca 64-bitową losowość i używa testu odrzucania.

package main

import "fmt"
import "time"

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

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
Riking
źródło
1
jeśli użyjesz, import."math/rand"to Int31jest dostępny w globalnej przestrzeni nazw i możesz zapisać 4 bajty, intgwarantuje również co najmniej 32 bity, oszczędzając ci kolejne 6 bajtów
Kristoffer Sall-Storgaard
Użyj :=składni dla kolejnych 3 bajtów
Kristoffer Sall-Storgaard
Użycie int zamiast int32 nie oszczędza żadnych bajtów, ponieważ musimy rzutować wynik Int31 () - 3 * int + () = 11 bajtów w porównaniu z 2 * int32 = 10 bajtów.
Riking
1
Nie trzeba rzucać, Int()w pakiecie rand znajduje się funkcja, można też usunąć miejsce późniejimport
Kristoffer Sall-Storgaard