Wählen Sie eine Zufallszahl zwischen 0 und n unter Verwendung einer konstanten Zufallsquelle

26

Aufgabe

Bei einer positiven Ganzzahl, die nkleiner als 2^30die von Ihnen als Eingabe angegebene ist, sollte Ihr Code eine zufällige Ganzzahl zwischen 0und neinschließlich ausgeben . Die von Ihnen generierte Zahl sollte einheitlich und zufällig gewählt werden . Das heißt, jeder Wert von 0bis nmuss mit gleicher Wahrscheinlichkeit auftreten (siehe Regeln und Vorsichtsmaßnahmen).

Regeln und Vorsichtsmaßnahmen

Ihr Code kann davon ausgehen, dass jeder in Ihre Sprache oder Standardbibliothek eingebaute Zufallszahlengenerator, der behauptet, gleichmäßig zufällig zu sein, tatsächlich gleichmäßig ist. Das heißt, Sie müssen sich keine Gedanken über die Qualität der von Ihnen verwendeten Zufallsquelle machen. Jedoch,

  • Sie müssen feststellen, dass Ihr Code eine einheitliche Zufallszahl von 0bis korrekt ausgibt, wenn die von Ihnen verwendete Zufallsquelle einheitlich ist n.
  • Alle Argumente beim Aufrufen einer eingebauten oder einer zufälligen Bibliotheksfunktion müssen konstant sein. Das heißt, sie müssen völlig unabhängig vom Eingabewert sein.
  • Ihr Code wird möglicherweise mit Wahrscheinlichkeit 1 beendet, anstatt garantiert zu werden, dass er beendet wird.

Anmerkungen

  • randInt(0,n) ist ungültig, da die Eingabe als Argument für eine eingebaute Funktion oder eine Bibliotheksfunktion verwendet wird.
  • rand()%nwird im Allgemeinen keine einheitliche Zufallszahl geben. Wenn intmax == 15und n = 10, als ein Beispiel von betseg, dann werden Sie viel wahrscheinlicher bekommen 0-5als 6-10.
  • floor(randomfloat()*(n+1)) gibt auch im Allgemeinen keine einheitliche Zufallszahl an, da es endlich viele verschiedene mögliche Gleitkommawerte zwischen 0 und 1 gibt.
total menschlich
quelle
Wie können Sie sicherstellen, dass die Ausgabe gleichmäßig zufällig ist? Es kann sein, dass eine bestimmte Sprache / Bibliothek einheitlich zufällige Zahlen ausgibt, eine Manipulation jedoch zu einer nicht einheitlichen Ausgabe führen kann. (ZB rng()bietet 0- 100, wenn n = 75und Funktion ist rng()%75, dann 0-25 wird häufiger ...)
Baldrickk
1
@Baldrickk Durch die Weisheit der Menge :) Wir können nur den Code lesen und darüber nachdenken.
Die traurige Schlussfolgerung, eine möglichst einfache wahrscheinlichkeitstheoretische Frage zu stellen: Zufälligkeit und Wahrscheinlichkeit sind sehr schlecht verstanden. :( (Und Regeln zu lesen ist anscheinend schwer.)
Martin Ender
Das
fällt
Warum haben Sie die x86-Antwort akzeptiert, wenn es drei kürzere gibt?
Dennis

Antworten:

25

x86-Maschinen mit rdrandAnweisung, 10 Bytes

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

Maschinensprache

0FC7F0 73FB 39F8 77F7 C3

Der Eingang befindet sich im Register rdiund der Ausgang in rax.
Dies respektiert die SYS V AMD64 ABI, so dass der Code effektiv eine C-Funktion implementiert

unsigned int foo(unsigned int max); 

mit 32-Bit-Ints.

Die Anleitung rdrandwird von Intel beschrieben

RDRANDgibt Zufallszahlen zurück, die von einem kryptografisch sicheren, deterministischen Zufallsbitgenerator DRBG geliefert werden. Der DRBG erfüllt den NIST SP 800-90A- Standard.

Der Umgang mit CSRNG impliziert, dass die Verteilung ohnehin einheitlich ist, wobei der NIST SP 800-90A zitiert wird:

Eine Zufallszahl ist eine Instanz einer unverfälschten Zufallsvariablen, dh die Ausgabe, die durch einen gleichmäßig verteilten Zufallsprozess erzeugt wird.


Die Prozedur generiert eine Zufallszahl und wenn sie nicht unbedingt größer als die Eingabe ist, wird sie zurückgegeben.
Andernfalls wird der Vorgang wiederholt.

Da eaxes sich um 32-Bit handelt, wird rdrandeine Zahl zwischen 0 und 2 32 -1 zurückgegeben, sodass für jedes n in [0, 2 32 -1] die Anzahl der erwarteten Iterationen 2 32 / (n + 1) beträgt, die für alle n definiert sind in [0, 2 30 ).

Margaret Bloom
quelle
Genial niedriger Pegel. Vielen Dank.
Wofür ist das jnc?
14.
@ l4m2 rdrandlegt fest, CFob die zurückgegebenen Daten gültig sind. Daten sind möglicherweise ungültig, weil zu viele Anforderungen den Entropiepool geleert haben. Siehe den manuellen Eintrag für rdrand und dies .
Margaret Bloom
20

Gelee , 7 6 Bytes

⁴!!X%‘

Vielen Dank an @JonathanAllan für das Abschlagen von 1 Byte!

Kann nicht auf TIO ausgeführt werden, da (16!)! ist eine riesige Zahl.

Wie es funktioniert

⁴!!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
quelle
Dies ist eine feste Version meiner gelöschten Antwort, die gleiche Idee. Obwohl ich eine unnötige Potenzierung hatte.
Orlp
Entschuldigung, ich habe es mir vor dem Posten nicht angesehen.
Dennis
Oh, das ist egal, ich hatte sowieso nicht vor, es zu reparieren. Ich fühle mich mit Jelly zu unwohl, um wirklich damit herumzuspielen.
Orlp
1
"Sir, ich weiß nicht, warum Sie verrückt sind. Der Algorithmus ist eine konstante Zeit. Das ist eine gute Sache, richtig? Warum sind Sicherheit und Personalwesen außerhalb der Tür?"
corsiKa
1
Einverstanden. Ein Unterschied zwischen einer 8-stelligen und einer 417-Billionen-stelligen Zahl: p
Jonathan Allan
11

Mathematica, 29 Bytes

Basierend auf Dennis 'Jelly-Antwort .

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

Ich würde nicht empfehlen, dies tatsächlich auszuführen. 2e9!ist eine ziemlich große Zahl ...

Es erweist sich als am kürzesten, eine riesige Zahl zu generieren, die durch alle möglichen Eingaben teilbar ist, und das Ergebnis mit einem einfachen Modulo auf den gewünschten Bereich abzubilden.

Ablehnungsabtastung, 34 Bytes

Mein alter Ansatz, der zu etwas interessanterem Code führte:

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

Grundlegende Stichprobenentnahme bei Ablehnung. Wir initialisieren die Ausgabe auf 13! (das ist größer als die maximale Eingabe 2 30 ) und ersetzen Sie es dann wiederholt durch eine zufällige ganze Zahl zwischen 0 und 13! solange der Wert größer als die Eingabe ist.

Martin Ender
quelle
1
Meinen Sie "kleiner als oder gleich dem Eingang"?
1
@Lembik Nein. Wir möchten den Wert neu generieren, solange er nicht in den gewünschten Bereich fällt.
Martin Ender
Oh ich verstehe. Aus irgendeinem Grund dachte ich, wir würden wiederholt Proben aus dem gewünschten Bereich entnehmen. Vielen Dank.
1
Erinnere mich daran, das nächste Mal ein Zeitlimit hinzuzufügen :)
9

Brachylog , 9 Bytes

≥.∧13ḟṙ|↰

Probieren Sie es online!

Dies wird 13!wie in Martin Enders Antwort verwendet ( 13ḟist ein Byte weniger als 2^₃₀).

implementiert wird mit random_between/3, der beim Ausgraben seiner Quelle verwendet, random_float/0welche mit random/1welcher verknüpft ist, den für unsere Zwecke einheitlichen Mersenne-Twister-Algorithmus verwendet.

Erläuterung

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

Prolog (SWI) , 38 Bytes

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

Funktioniert durch Ablehnungsabtastung.

Erzeugen Sie eine Zufallszahl zwischen 0 und 2 ^ 31-1 = 2147483647 bis eine kleiner oder gleich der Eingabe ist.

Ich habe das Gefühl, dass ich in der Lage sein sollte, einen Schnitt anstelle des anderen zu verwenden, aber ich kann nicht sehen, wie.

Emigna
quelle
1
Sie könnten die Verwendung von else vermeiden repeat, aber es endet damit, dass es 3 Bytes länger ist. Ich bin mir nicht sicher, ob es einen kürzeren Weg gibt, unendlich viele Auswahlpunkte zu haben als zu wiederholen.
Fatalize
@Fatalize: Ja, ich habe es auch versucht. Ich hatte die Erinnerung, dass ich so etwas benutzt habe ,!., um einen Backtrack zu erzwingen, aber entweder erinnere ich mich daran, dass es falsch war, oder es ist für diese Lösung nicht anwendbar.
Emigna
7

Labyrinth , 63 Bytes

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

(Danke an @MartinEnder für die Hilfe beim heftigen Golfen hier.)

Labyrinth ist eine 2D-Sprache und die einzige Quelle für Zufälligkeiten ist eine Situation wie die folgende:

   x
  "<)
 " "
 " "

Angenommen, der Anweisungszeiger befindet sich auf xund bewegt sich nach unten. Es landet als nächstes auf dem <, was, wenn der obere Teil des Stapels 0 ist (was im obigen Programm immer der Fall ist), die aktuelle Zeile um 1 nach links verschiebt:

   "
 "<)
 " "
 " "

Der Befehlszeiger befindet sich jetzt auf der < unten. An einer Kreuzung dreht sich das Labyrinth basierend auf der Stapelspitze - Negativ ist links, Positiv ist rechts und Null ist vorwärts. Wenn die Spitze des Stapels zu diesem Zeitpunkt immer noch Null ist, können wir uns nicht vorwärts oder rückwärts bewegen, da es keinen Pfad gibt, sodass Labyrinth mit gleicher Wahrscheinlichkeit zwischen Links- und Rechtskurven zufällig wechselt.

Im Wesentlichen verwendet das obige Programm die Zufallsfunktion, um 100-Bit-Zahlen (100, die #00hier angegeben sind) zu generieren und die Schleife fortzusetzen, bis eine Zahl generiert wird <= n.

Zum Testen wird es wahrscheinlich hilfreich sein, #0"stattdessen 10-Bit-Zahlen zu verwenden, wobei "es sich um einen No-Op-Pfad handelt. Probieren Sie es online!

Grobe Erklärung:

 ?            <--- ? 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
quelle
7

Python, 61 Bytes

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

Bearbeiten: Aktualisiert, um verbotene Form zu vermeiden

Edit2: 2 Bytes gespeichert, danke @ JonathanAllan

Edit3: Bezahlt 2 Bytes für eine voll funktionsfähige Lösung - Nochmals vielen Dank an JonathanAllan

Edit4: entfernt f= , spart 2 Bytes

Edit5: 1 weiteres Byte dank @ gespeichert JonathanAllan

Edit6: 2 weitere Bytes dank @ gespeichert JonathanAllan

Inzwischen wies mich die Schuld auf die schlechten Dinge und JonathanAllan auf das, was hilft.

Edit7: Wenn es regnet, gießt es - weitere 2 Bytes

Edit8: Und noch 2 Bytes

Ich wurde von Agrue gegessen
quelle
1
Dies wird nie ausgegeben n, aber Sie können zwei Bytes sparen, wenn Sie dies beheben, indem Sie das verwenden from random import*und löschen r..
Jonathan Allan
1
Ja, Sie können den "Kaulquappenoperator" verwenden, um die sonst erforderlichen Klammern zu vermeiden, also ...*(-~n*1.0/2**30))nicht...*((n+1)*1.0/2**30))
Jonathan Allan
1
"Ja wirklich?" Süss! Haben Sie einen langjährigen Groll gegen die Nummer 70? Vielen Dank für Ihre Hilfe
iwaseatenbyagrue
1
In der Tat randrangescheint ein Float zu akzeptieren, also lambda n,x=2.**30:int(randrange(x)*-~n/x)spart noch zwei [edit ...] vier!
Jonathan Allan
1
^ Noch zwei mit Klammern. Nur um zu zeigen, dass Ihre Multiplikation der richtige Weg war!
Jonathan Allan
6

Python 2 , 61 Bytes

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

Pseudozufällig wählt Ganzzahlen zwischen 0 und k für alle Werte von k zwischen 0 und 2 31 - 2 aus und nimmt dann die Ganzzahl entsprechend k = n .

Dennis
quelle
5

Batch, 64 Bytes

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

%random%gibt nur 15 Bits der Zufälligkeit, also muss ich zwei Zufallszahlen kombinieren. Schleifen, bis der Zufallswert im gewünschten Bereich liegt, also langsam für niedrig n; 98 Bytes für eine schnellere Version:

@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
quelle
Der Code ist zwar langsam, aber Ihre Antwort war schnell!
3
@Lembik Ich hatte die Antwort bereit, in Ihrer gelöschten Frage zu gehen ...
Neil
Wird dies nicht zuerst die gewünschte Nummer und dann alle anderen Nummern wiedergeben, die größer wurden als n?
Erik der Outgolfer
@EriktheOutgolfer Nein; Wenn Sie callkein Batch-Skript aufrufen, wird das aktuelle Skript beendet.
Neil
5

MATL , 12 Bytes

Vielen Dank an @AdmBorkBork und @Suever , die mir mitgeteilt haben , wie der TIO-Cache deaktiviert werden kann.

`30WYrqG>}2M

Probieren Sie es online! .

Hierbei wird eine Ablehnungsmethode verwendet : Erzeugen Sie eine zufällige Ganzzahl von 0bis 2^30-1und wiederholen Sie diese, solange sie die Eingabe überschreitet n. Dies wird garantiert mit einer Wahrscheinlichkeit enden 1, aber die durchschnittliche Anzahl von Iterationen ist 2^30/nund daher dauert es sehr lange, bis es nerheblich kleiner ist als 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
quelle
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)

Erzeugt Ganzzahlen im Bereich [0 ... 2 k - 1] , wobei k die kleinste Ganzzahl ist, sodass 2 k größer als n ist . Wiederholt sich, bis das Ergebnis in [0 ... n] fällt .

Warum?

Dies basiert auf folgenden Annahmen:

  • Intern die von der JS-Engine generierten pseudozufälligen Ganzzahlwerte zum Feeden Math.random() über ein beliebiges Intervall [0 ... 2 k -1] (mit k <32 ) einheitlich .

  • Einmal mit einer exakten Potenz von 2 multipliziert, sind die von zurückgegebenen IEEE 754-Gleitkommawerte Math.random()über solche Intervalle hinweg immer noch einheitlich.

Wenn jemand diese Hypothesen bestätigen oder widerlegen kann, lassen Sie es mich bitte in den Kommentaren wissen.

Demo

Erzeugt 1 Million Werte in [0 ... 2] und zeigt die Ergebnisstatistik an.

Arnauld
quelle
Math.floor (Math.random () * (n + 1)) liefert für mich nicht weniger gleichmäßig verteilte Ergebnisse. Es wäre also schön zu sehen, ob es realistische N <2 ^ 30 gibt, die zu Verteilungsanomalien führen überhaupt.
Zeppelin
1
@zeppelin Sie würden viel zu viele Testläufe benötigen, um Anomalien zu lokalisieren, da ein zufälliger Gleitkommawert in diesem Bereich einen von 2 ^ 53 Werten aufweist, der so gleichmäßig wie möglich über die 2 ^ 30 Ergebnisse verteilt wird. Selbst für große Zahlen im Bereich ist der Fehler etwa 1 zu 2 ^ 23, was bedeutet, dass Sie eine lächerliche Anzahl von Versuchen benötigen. Sie werden wahrscheinlich ein paar Größenordnungen mehr wollen als die Anzahl der ersten Samples (2 ^ 53). Dennoch kann es nicht vollkommen gleichmäßig sein, wenn der Multiplikator die Anzahl der Abtastwerte nicht gleichmäßig aufteilt, weshalb Arnauld eine Zweierpotenz verwendet.
Martin Ender
4

Bash (+ Coreutils), 44 Bytes

/ dev / urandom basierte Lösung

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

Liest vorzeichenlose 32-Bit-Ganzzahlen aus /dev/urandomund filtert sie heraus, awkbis eine innerhalb eines bestimmten Bereichs gefunden wird. Anschließend sed qwird die Pipe abgebrochen.

Zeppelin
quelle
Hurra für die Bash :)
4

Haskell, 70 Bytes

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

Kein sehr effizienter Algorithmus, aber er funktioniert. Es generiert eine unendliche Liste von Ganzzahlen (oder Gleitkommazahlen, falls erforderlich, aufgrund des Haskell-Typensystems), die durch [0,2 ^ 30] begrenzt sind, und nimmt die erste Zahl kleiner oder gleich n. Für kleine n kann dies lange dauern. Die Zufallszahlen sollten gleichmäßig verteilt sein, wie in der Dokumentation für randomR angegeben, damit alle Zahlen im Intervall [0,2 ^ 30] die gleiche Wahrscheinlichkeit haben (1 / (2 ^ 30 + 1)), also alle Zahlen in [ 0, n] haben die gleiche Wahrscheinlichkeit.

Alternative Version:

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

Diese Version ist schrecklich, spart aber ein ganzes Byte. randomsVerwendet einen willkürlichen Bereich, der vom Typ definiert wird, um eine unendliche Liste von Zahlen zu generieren. Dies kann Negative beinhalten, daher müssen wir es mit abbilden abs, um sie positiv (oder null) zu machen. Dies ist extrem langsam für alle Werte von n, die nicht absurd groß sind. BEARBEITEN : Ich habe später festgestellt, dass diese Version nicht gleichmäßig verteilt ist, da die Wahrscheinlichkeit, 0 zu erhalten, aufgrund der Verwendung von schlechter als die anderen Zahlen ist abs. Um eine Zahl zu erzeugen m, könnte der Generator eine Zahl erzeugen moder -maber im Fall von 0 funktioniert nur 0 selbst, daher ist seine Wahrscheinlichkeit die Hälfte der anderen Zahlen.

user1472751
quelle
Hurra für Haskell (auch)!
4

Gelee , 9 Bytes

⁴!Ẋ’>Ðḟ⁸Ṫ

Probieren Sie es online!- Der obige Code wird nicht auf TIO ausgeführt, da es sich um einen Bereich der Größe 16 handelt! muss zuerst erstellt werden (ganz zu schweigen von der Tatsache, dass sie dann gemischt und dann gefiltert werden müssen!), so ist dies dasselbe in einem viel kleineren Maßstab, der 30 Mal für eine Eingabe von 3 mit einer Schranke von 10 wiederholt wird.

Wie?

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

Hinweis: Es wäre mehr als tausend Mal effizienter, wenn man ȷ⁵bei gleicher Byteanzahl das tun würde, was man naiv erwarten würde, und zehn zu zehn zurückgeben würde. Dies ist jedoch nicht der Fall, da die nicht als zu verwendende wörtliche Zehn ausgewertet wird Nach dem Zahlenliteral werden ȷ...jedoch zwei separate Literale analysiert, ȷwobei der Standardexponent von drei eintausend und zehn ergibt.

Jonathan Allan
quelle
Huh, das sind 9 Zeichen, aber 22 Bytes
Kristoffer Sall-Storgaard
@ KristofferSall-Storgaard Jedes Zeichen ist eines der 256 Bytes in Jellys Codepage . Ich habe vergessen, die Wortbytes wie gewohnt zu verknüpfen.
Jonathan Allan
1
Jahr habe ich es nachgeschlagen und gleich rausgefunden
Kristoffer Sall-Storgaard
4

JDK 9 auf jshell, 75 59 Bytes

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

Verwendung

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 Bytes: Danke Jakob!
  • Angenommen, wir betrachten jshell als eine gültige Laufzeitumgebung.
  • jshell selbst erfordert als Laufzeitumgebung keinen expliziten Import für Kernbibliotheken und keine Semikolons.
  • Liefert ein OptionalInt. Die Regeln legen nicht fest, dass der Rückgabetyp ein Grundelement sein muss, und ich halte eine OptionalIntfür eine gültige Darstellung des Ergebnisses.
Pete Terlep
quelle
1
Vielen Dank an @ kevin-cruijssen für die Inspiration. Mein erster Code Golf!
Pete Terlep
Ob eine Box-Ausgabe akzeptiert wird oder nicht, unterscheidet sich davon, ob eine Optionalakzeptiert wird. Ich würde mit dem Plakat bestätigen, wenn ich du wäre. Es ist auch nicht erforderlich, die gesamte Aufgabe zu zählen. nur der Lambda-Ausdruck ist ausreichend.
Jakob
1
Sie können 4 Bytes sparen, indem Sie die Klammern um den Lambda-Parameter nund entfernen new Random().
Jakob
3

PHP, 30 Bytes

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

Laufen Sie mit echo <N> | php -Rn '<code>'.

wählt eine Zufallszahl zwischen 0 und getrandmax()(2 ** 31-1 auf meiner 64-Bit-Maschine);
wiederholt sich, während das größer als die Eingabe ist.

Dies kann eine Weile dauern ... mein AMD C-50 (1 GHz) benötigte zwischen 0,3 und 130 Sekunden für N=15.

Ein schnellerer Weg für den Durchschnitt N( 46 Bytes ):

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

oder

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

nimmt N+1zufällige ganze Zahlen, summiert sie und nimmt das Modulo mit N+1.
Der C-50 benötigt ca. 8 Sekunden für 1 Million Läufe.

Eine ungültige Lösung für 19 Bytes :

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

PowerShell , 35 Byte

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

Probieren Sie es online!

Eine weitere Methode zur Probenahme bei Ablehnung. Hierbei handelt es sich um eine forEndlosschleife, bei der der Wert von $aals RandomGanzzahl zwischen 0und 1gb( = 1073741824 = 2^30) festgelegt wird. Die Schleife wird so lange -gfortgesetzt, wie diese Ganzzahl an tder Eingabe anliegt $args. Sobald die Schleife abgeschlossen ist, setzen wir einfach $adie Pipeline ein und die Ausgabe ist implizit.

Hinweis: Dies dauert lange, wenn die Eingabe eine kleine Zahl ist.

AdmBorkBork
quelle
3

Python 2 , 72 69 Bytes

-3 Bytes dank xnor (überschreibe die ideingebaute als Variable)

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

Probieren Sie es online!

randrange(2**30)erzeugt eine pseudo-gleichmäßig verteilte Zahl (Mersenne Twister 2 19937-1 ) aus dem Bereich [0,2 30 ) . Da ngarantiert weniger als 2 30 ist, kann dies einfach wiederholt aufgerufen werden, bis es nicht mehr als die Eingabe ist. Bei sehr niedrigen Werten von dauert es eine lange erwartete Zeit n, funktioniert jedoch normalerweise innerhalb einer Minute, selbst bei Eingaben von nur 50.

Jonathan Allan
quelle
2
Sie können r=''als "unendlich" initialisieren . Oder, noch besser, initialisieren Sie es nicht rund verwenden Sie es stattdessen idüberall für r.
28.
2

05AB1E , 11 Bytes

žIÝ.rDI›_Ϥ

Probieren Sie es online!

Erläuterung

ž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

Da die Liste [0 ... 2147483648]für TIO zu groß ist, wird 1.000.000stattdessen der Link verwendet .

Alternative (im Durchschnitt) viel schnellere 11-Byte-Lösung

[žIÝ.RD¹›_#

Probieren Sie es online aus

Erläuterung

[             # 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
quelle
žJL.R%für 6, es sei denn, ich vermisse etwas riesiges. Drücken Sie 2 ^ 32, Liste von 0 bis 2 ^ 32, zufällige Auswahl. Modulo-Eingang. Wird absolut die Effizienz schrauben, die Sie haben.
Magic Octopus Urn
@ carusocomputing. Sie müssten Idort ein für 7 Bytes, um die Argumente für Modul in der richtigen Reihenfolge (und vielleicht Ýstatt L) zu erhalten, aber ansonsten ist das sicherlich eine kürzere Lösung. Ich sah Dennis das in seiner Gelee-Antwort tun, aber da dies meine erste Idee war, behielt ich dies bei. Da sich dieser Ansatz von diesem unterscheidet, können Sie ihn als separate Antwort veröffentlichen.
Emigna
DI‹Ï würde die Schleife vermeiden.
Magic Octopus Urn
Es ist auch nicht garantiert, dass dies so wie es ist endet. Wenn ich mich nicht irre, würde eine Eingabe von 0fast immer zu einer nahezu unendlichen Schleife führen, was das Beenden erschwert. Obwohl die Lösung die Möglichkeit bietet, in allen Szenarien zu kündigen, wird dies aufgrund von Zufälligkeiten nicht garantiert.
Magic Octopus Urn
@carusocomputing: Bei sehr kleinen Eingaben würde die zweite Version im Durchschnitt sehr lange brauchen, um ja fertig zu werden, aber bei genügend Zeit würde es dauern.
Emigna
2

Python 2, 89 Bytes

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

Erläuterung

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.

Dies ist sehr ineffizient, da 2 ^ 31 Ganzzahlen erstellt, gemischt und gefiltert werden.

Ich sehe keinen Grund darin, einen TIO-Link zu teilen, über den so große Listen erstellt werden. Deshalb hier ein TIO-Link für n = 100.

Probieren Sie es online!

Yytsi
quelle
2

Java 8, 84 83 80 71 62 Bytes

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

-1 Byte danke an @ OliverGrégoire .
-3 Bytes dank @Jakob .
-9 Bytes Konvertieren von Java 7 nach Java 8.
-9 Bytes durch Ändern java.util.Random().nextInt(1<<30)in(int)(Math.random()*(1<<30)) .

Erläuterung:

Probieren Sie es hier aus.

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

HINWEIS: Bei kleinen Eingaben kann dies offensichtlich sehr lange dauern.

Beispielausgabe:

407594936
Kevin Cruijssen
quelle
2
@Aaron Ich habe dies ebenfalls in Frage gestellt, sehe aber den zweiten Aufzählungspunkt: "Alle Argumente beim Aufrufen einer eingebauten oder Bibliotheks-Zufallsfunktion müssen konstant sein. Das heißt, sie müssen vollständig unabhängig vom Eingabewert sein." Dies ist der Grund, warum max int verwendet wird.
Poke
1
2^30= 1073741824. Du hast es vorgezogen -1>>>1(= 2147483647) zu verwenden. Aber das gibt es: 1<<30was genau gleich ist 2^30; und ist 1 Byte kürzer.
Olivier Grégoire
1
Wie wäre es int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}?
Jakob
@ Jakob Danke. Ich habe es sogar um 18 weitere Bytes gekürzt, indem ich Java 8 anstelle von 7 und Math.random()anstelle von verwendet habe java.util.Random().nextInt.
Kevin Cruijssen
2

Python 3, 51 Bytes

Hier ist eine Python-Lösung mit einer unorthodoxen Zufallsquelle.

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

Probieren Sie es online!

Also, um das aufzubrechen.

int(input())+1

Ruft die eingegebene Nummer ab und fügt 1sie hinzu.

set(range(...))

Erstellt den Satz {0, 1, 2, 3, 4, ... n}für alle möglichen Ergebnisse.

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

Nimmt das Set, konvertiert es in eine Liste und greift nach dem ersten Objekt.

Dies funktioniert, weil in Python 3 die Reihenfolge von set()durch PYTHONHASHSEED festgelegt wird ( kann nicht abgerufen werden , wird aber bei der Skriptausführung festgelegt).

Zugegeben, ich vermute, dass dies eine gleichmäßige Verteilung ist, da der hash()Wert zufällig zugewiesen wird und ich den Wert mit einem bestimmten zufällig auswähle hash(), anstatt nur den Wert hash(input())selbst zurückzugeben.

Wenn jemand weiß, ob es sich um eine Gleichverteilung handelt oder wie ich das testen könnte, kommentieren Sie bitte.

Der Matt
quelle
1

C #, 57 Bytes

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

Anonyme Funktion, die eine Ganzzahl zwischen 0 und n einschließlich zurückgibt.

Je kleiner die eingegebene Zahl ist, desto länger dauert es, einen Zufallswert zurückzugeben.

Volles Programm:

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
quelle
2
"Alle Argumente beim Aufrufen einer eingebauten oder Bibliothekszufallsfunktion müssen konstant sein. Das heißt, sie müssen vollständig unabhängig vom Eingabewert sein." Das Argument zu Nextist nicht statisch.
Yytsi
1

Bash + Coreutils, 20 Bytes

Golf gespielt

seq 0 $ 1 | shuf | sed 1q

shuf - erzeugt zufällige Permutationen

Shuf wird den folgenden Code verwenden : um Permutationen zu generieren:

permutation = randperm_new (randint_source, head_lines, n_lines);

was endet in 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.  */
      ...
}

Dies wiederum liest ein paar Bytes der Zufallsdaten aus der Quelle der Zufälligkeit auf niedriger Ebene:

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

dh auf der niedrigen Ebene gibt es keine direkte Abhängigkeit zwischen dem shufEingabewert und den aus der Zufallsquelle gelesenen Daten (abgesehen von der Berechnung der erforderlichen Byte-Pufferkapazität).

Zeppelin
quelle
6
Gibt das nicht die Eingabe als Argument für Ihren Zufallszahlengenerator?
Martin Ender
Auch wenn dies nicht gültig ist, senden Sie uns bitte eine weitere Bash-Antwort!
@MartinEnder gut, nicht direkt, es verwendet nur die Eingabe, um die Obergrenze für den generierten Integer-Bereich zu definieren und jot will arrange for all the values in the range to appear in the output with an equal probability(das ist wahrscheinlich grenzwertig, aber immer noch).
Zeppelin
2
Wenn ich tief genug in einen Zufallsgenerator greife, finde ich sicher einen Aufruf für ein RNG auf niedrigerer Ebene, das das ursprüngliche Argument nicht direkt verwendet. Die Herausforderung besteht darin, eine gleichmäßige Verteilung mit beliebiger Größe aus einer Verteilung mit fester Größe zu erhalten, was Sie immer noch nicht tun.
Martin Ender
1

SmileBASIC, 38 Bytes

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

Erzeugt Zufallszahlen, bis eine kleiner als die Eingabe ist.

12Me21
quelle
1

Ruby, 23 15 23 32 29 Bytes

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

Wie es funktioniert:

  • 1while [...];Führt die Anweisung mindestens einmal aus: 1before whilefungiert als NOP
  • Erhalte eine Zufallszahl im Bereich 0..2 ^ 30-1 ( niedriger als 2 ^ 30 , wie angegeben)
  • Wiederholen Sie diesen Vorgang, wenn die Zahl höher als der Eingabeparameter ist. (Kann einige Zeit dauern, wenn n klein ist.)
GB
quelle
1

Ohm, 26 Bytes

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

Erläuterung:

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
quelle
Gibt es einen Dolmetscher für diese Sprache? Und was ist mit Code-Seite?
ATaco
@ATaco: Interpreter , Code-Seite: CP-437
Emigna
1

Golang, 84 78 71 Bytes

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

Einfache Rückweisungsentnahme.

Hinweis: Da der Startwert für math / rand eine konstante 1 ist, muss der Aufrufer den Startwert festlegen, es sei denn, ein konstantes Ergebnis wird gewünscht.

Test: https://play.golang.org/p/FBB4LKXo1r Auf einem 64-Bit-System praktisch nicht mehr testbar, da es 64-Bit-Zufälligkeit zurückgibt und Ablehnungstests verwendet.

package main

import "fmt"
import "time"

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

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
Riking
quelle
1
Wenn Sie import."math/rand"dann verwenden, Int31ist es im globalen Namespace verfügbar und Sie können 4 Bytes speichern, es sind auch intmindestens 32 Bits garantiert, wodurch Sie weitere 6 Bytes sparen
Kristoffer Sall-Storgaard
Verwenden Sie die :=Syntax für weitere 3 Bytes
Kristoffer Sall-Storgaard
Die Verwendung von int anstelle von int32 speichert keine Bytes, da das Ergebnis von Int31 () - 3 * int + () = 11 Bytes gegenüber 2 * int32 = 10 Bytes umgewandelt werden muss.
Riking
1
Keine Notwendigkeit zu besetzen, es gibt eine Int()Funktion im Rand-Paket, außerdem können Sie das Leerzeichen nachher entfernenimport
Kristoffer Sall-Storgaard