Elija un número aleatorio entre 0 yn usando una fuente constante de aleatoriedad

26

Tarea

Dado un número entero positivo nmenor que el 2^30especificado como entrada en cualquier forma que elija, su código debería generar un número entero aleatorio entre 0e n, inclusive. El número que genere debe elegirse uniformemente al azar . Es decir, cada valor de 0a ndebe ocurrir con la misma probabilidad (ver Reglas y Advertencias).

Reglas y advertencias

Su código puede suponer que cualquier generador de números aleatorios integrado en su idioma o biblioteca estándar que afirma ser uniformemente aleatorio es de hecho uniforme. Es decir, no tiene que preocuparse por la calidad de la fuente aleatoria que está utilizando. Sin embargo,

  • Debe establecer que si la fuente aleatoria que está utilizando es uniforme, entonces su código genera correctamente un entero aleatorio uniforme de 0a n.
  • Cualquier argumento al llamar a una función aleatoria integrada o de biblioteca debe ser constante. Es decir, deben ser completamente independientes del valor de entrada.
  • Su código puede terminar con probabilidad 1 en lugar de estar garantizado para terminar.

Notas

  • randInt(0,n) no es válido ya que toma la entrada como argumento para una función incorporada o biblioteca.
  • rand()%nserá no dar un número aleatorio uniforme en general. A modo de ejemplo dado por betseg, si intmax == 15y n = 10, a continuación, que será mucho más probable conseguir 0-5que 6-10.
  • floor(randomfloat()*(n+1)) tampoco dará un número aleatorio uniforme en general debido al número finito de diferentes valores posibles de coma flotante entre 0 y 1.
totalmente humano
fuente
¿Cómo va a confirmar que la salida es uniformemente aleatoria? Puede ser que un idioma / biblioteca dado produzca números aleatorios uniformes, pero la manipulación podría dar como resultado una salida no uniforme. (por ejemplo, rng()proporciona 0- 100, si n = 75, y la función es rng()%75, entonces 0-25 será más común ...)
Baldrickk
1
@Baldrickk Por la sabiduría de las multitudes :) Solo podemos leer el código y pensarlo.
La triste conclusión de hacer la pregunta de teoría de probabilidad más simple posible: la aleatoriedad y la probabilidad son muy poco conocidas. :( (Y leer las reglas es difícil, aparentemente.)
Martin Ender
Esto viene a mi mente: Número aleatorio
BgrWorker
¿Por qué aceptaste la respuesta x86 cuando hay tres más cortas?
Dennis

Respuestas:

25

Máquinas x86 con rdrandinstrucciones, 10 bytes

BITS 64

_try_again:

 rdrand eax
jnc _try_again

 cmp eax, edi
ja _try_again

 ret

codigo de maquina

0FC7F0 73FB 39F8 77F7 C3

La entrada está en el registro rdiy la salida en rax.
Esto respeta el SYS V AMD64 ABI, por lo que el código implementa efectivamente una función C

unsigned int foo(unsigned int max); 

con entradas de 32 bits.

rdrandIntel describe la instrucción

RDRANDdevuelve números aleatorios que son suministrados por un generador de bits aleatorio determinista criptográficamente seguro DRBG. El DRBG está diseñado para cumplir con el estándar NIST SP 800-90A .

Al tratar con CSRNG, está implícito que la distribución es uniforme, de todos modos, citando el NIST SP 800-90A:

Un número aleatorio es una instancia de una variable aleatoria imparcial, es decir, la salida producida por un proceso aleatorio distribuido uniformemente .


El procedimiento genera un número aleatorio y, si no es estrictamente mayor que la entrada, se devuelve.
De lo contrario, el proceso se reitera.

Como eaxes de 32 bits, rdranddevuelve un número entre 0 y 2 32 -1, por lo que por cada n en [0, 2 32 -1] el número de iteraciones esperadas es 2 32 / (n + 1) que se define para todos los n en [0, 2 30 ).

Margaret Bloom
fuente
Brillantemente bajo nivel. Gracias.
¿Qué es la jncde?
l4m2
@ l4m2 rdrandestablece CFsi los datos devueltos son válidos. Los datos pueden no ser válidos porque demasiadas solicitudes agotaron el grupo de entropía. Vea la entrada manual para rdrand y esto .
Margaret Bloom
20

Gelatina , 7 6 bytes

⁴!!X%‘

¡Gracias a @JonathanAllan por jugar golf en 1 byte!

No se puede ejecutar en TIO porque (16!)! Es un gran número.

Cómo funciona

⁴!!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
fuente
Esta es una versión fija de mi respuesta eliminada, la misma idea. Aunque tuve una exponenciación innecesaria.
orlp
Lo siento, no lo miré antes de publicar.
Dennis
Oh, no importa, no estaba planeando arreglarlo de todos modos. Estoy demasiado incómodo con Jelly para realmente jugar con él.
orlp
1
"Señor, no sé por qué está enojado. El algoritmo es tiempo constante. Eso es algo bueno, ¿verdad? ¿Por qué la seguridad y los recursos humanos están fuera de la puerta?"
corsiKa
1
Convenido. Una pequeña diferencia entre un número de 8 dígitos y un número de 417 quintillones de dígitos: p
Jonathan Allan
11

Mathematica, 29 bytes

Basado en la respuesta de Dennis's Jelly .

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

No recomendaría realmente ejecutar esto. 2e9!es un número bastante grande ...

Resulta más corto generar un gran número que sea divisible por todas las entradas posibles y asignar el resultado al rango requerido con un módulo simple.

Muestreo de rechazo, 34 bytes

Mi antiguo enfoque que condujo a un código algo más interesante:

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

Muestreo básico de rechazo. ¡Inicializamos la salida a 13! (que es mayor que la entrada máxima 2 30 ) y luego reemplácelo repetidamente con un entero aleatorio entre 0 y 13. siempre que el valor sea mayor que la entrada.

Martin Ender
fuente
1
¿Quiere decir "menor o igual que la entrada"?
1
@Lembik No. Queremos regenerar el valor siempre que no se encuentre dentro del rango deseado.
Martin Ender
Oh ya veo. Por alguna razón, pensé que estábamos muestreando repetidamente del rango deseado. Gracias.
1
Recordarme agregar un límite de tiempo la próxima vez :)
9

Brachylog , 9 bytes

≥.∧13ḟṙ|↰

Pruébalo en línea!

Esto se usa 13!como en la respuesta de Martin Ender ( 13ḟes un byte menos que 2^₃₀).

se implementa utilizando random_between/3, que, al cavar su fuente, utiliza el random_float/0que está vinculado al random/1que utiliza el algoritmo Mersenne Twister que es uniforme para nuestros propósitos.

Explicación

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

Prólogo (SWI) , 38 bytes

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

Trabajos por muestreo de rechazo.

Genere un número aleatorio entre 0 y 2 ^ 31-1 = 2147483647 hasta que se encuentre uno menor o igual a la entrada.

Siento que debería poder usar un corte en lugar de otro, pero no puedo ver cómo.

Emigna
fuente
1
Podría evitar el uso de otra cosa repeat, pero termina siendo 3 bytes más largos ... No estoy seguro si hay una forma más corta de tener infinitos puntos de elección que repetir.
Fatalize
@Fatalize: Sí, intenté repetir también. Tenía un recuerdo de usar algo como ,!.forzar un retroceso, pero o lo recuerdo mal o no es aplicable a esta solución.
Emigna
7

Laberinto , 63 bytes

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

(Gracias a @MartinEnder por la ayuda con un poco de golf pesado aquí).

Labyrinth es un lenguaje 2D, y su única fuente de aleatoriedad se encuentra en una situación como la siguiente:

   x
  "<)
 " "
 " "

Suponga que el puntero de instrucción está en xy se mueve hacia abajo. Luego aterriza en el< , que si la parte superior de la pila es 0 (que siempre es el caso en el programa real anterior) desplaza la fila actual a la izquierda por 1:

   "
 "<)
 " "
 " "

El puntero de instrucciones ahora está en el < mueve hacia abajo. En un cruce, Labyrinth gira en función de la parte superior de la pila: lo negativo es girar a la izquierda, lo positivo es girar a la derecha y cero es avanzar. Si la parte superior de la pila sigue siendo cero en este punto, no podemos movernos hacia adelante o hacia atrás ya que no hay camino, por lo que Labyrinth se aleatorizará entre girar a la izquierda o girar a la derecha con la misma probabilidad.

Esencialmente, lo que hace el programa anterior es usar la función de aleatoriedad para generar números de 100 bits (100 especificados por #00 aquí) y continuar haciendo bucles hasta que genere un número <= n.

Para las pruebas, probablemente sea útil usar #0"en su lugar para números de 10 bits, siendo la "ruta no operativa.Pruébalo en línea!

Explicación aproximada:

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

Python, 61 bytes

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

Editar: actualizado para evitar la forma prohibida

Edit2: guardado 2 bytes, gracias @ JonathanAllan

Edit3: Pagué 2 bytes por una solución totalmente funcional, gracias de nuevo @JonathanAllan

Edit4: eliminado f=, ahorrando 2 bytes

Edit5: guardado 1 byte más gracias a @ JonathanAllan

Edit6: guardado 2 bytes más gracias a @ JonathanAllan

A estas alturas, la culpa de Git me señalaría por las cosas malas, y JonathanAllan por las cosas que ayudan.

Edit7: cuando llueve, llueve - otros 2 bytes

Edit8: y otros 2 bytes

iwaseatenbyagrue
fuente
1
Esto nunca saldrá n, pero puede guardar dos bytes cuando lo arregle usando from random import*y soltando r..
Jonathan Allan
1
Sí, puede usar el "operador renacuajo" para evitar los paréntesis que de otro modo serían necesarios, así que en ...*(-~n*1.0/2**30))lugar de...*((n+1)*1.0/2**30))
Jonathan Allan
1
De Verdad? ¡Dulce! ¿Tienes algún rencor de larga data contra el número 70? Muchas gracias por su ayuda
iwaseatenbyagrue
1
De hecho, randrangeparece aceptar un flotador, ¡así que lambda n,x=2.**30:int(randrange(x)*-~n/x)ahorra otros dos [editar ... cuatro]!
Jonathan Allan
1
^ otros dos con eliminación de paréntesis. ¡Solo muestra que su multiplicación era el camino a seguir!
Jonathan Allan
6

Python 2 , 61 bytes

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

Pseudo-azar elige números enteros comprendidos entre 0 y k para todos los valores de k entre 0 y 2 31 - 2 , entonces toma el número entero correspondiente a k = n .

Dennis
fuente
5

Lote, 64 bytes

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

%random%solo da 15 bits de aleatoriedad, por lo que tengo que combinar dos números aleatorios. Loops hasta que el valor aleatorio se encuentre dentro del rango deseado, tan lento para bajo n; 98 bytes para una versión más rápida:

@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
fuente
¡El código puede ser lento pero su respuesta fue rápida!
3
@Lembik Tenía la respuesta lista para ir en tu pregunta eliminada ...
Neil
¿No hará eco primero el número deseado, y luego todos los demás números que resultaron ser mayores que n?
Erik the Outgolfer
@EriktheOutgolfer No; a menos que lo use call, invocar un script por lotes termina el script actual.
Neil
5

MATL , 12 bytes

Gracias a @AdmBorkBork y a @Suever por decirme cómo deshabilitar el caché TIO.

`30WYrqG>}2M

Pruébalo en línea! .

Esto utiliza un método de rechazo : genera un número entero aleatorio de 0a 2^30-1, y repite mientras excede la entrada n. Se garantiza que esto terminará con probabilidad 1, pero el número promedio de iteraciones es 2^30/n, y por lo tanto, lleva mucho tiempo para nsignificativamente menor que 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
fuente
4

JavaScript (ES6), 55 54 bytes

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

Genera enteros en el rango [0 ... 2 k - 1] , donde k es el entero más pequeño de modo que 2 k es mayor que n . Se repite hasta que el resultado cae en [0 ... n] .

¿Por qué?

Esto se basa en los siguientes supuestos:

  • Internamente, los valores enteros pseudoaleatorios generados por el motor JS para alimentar Math.random()son uniformes en cualquier intervalo [0 ... 2 k -1] (con k <32 ).

  • Una vez multiplicado por una potencia exacta de 2, los valores de flotación IEEE 754 devueltos por Math.random()todavía son uniformes durante dichos intervalos.

Si alguien puede confirmar o refutar estas hipótesis, hágamelo saber en los comentarios.

Manifestación

Genera 1 millón de valores en [0 ... 2] y muestra las estadísticas de resultados.

Arnauld
fuente
Math.floor (Math.random () * (n + 1)) produce resultados no menos uniformemente distribuidos para mí, por lo que sería bueno ver si hay alguna N <2 ^ 30 realista, lo que producirá cualquier anomalía de distribución en absoluto.
zepelín
1
@zeppelin, necesitaría demasiadas ejecuciones de prueba para identificar cualquier anomalía, ya que un flotante aleatorio en ese rango tendrá uno de 2 ^ 53 valores que se distribuirán de la manera más uniforme posible en los resultados de 2 ^ 30. Entonces, incluso para números grandes en el rango, el error será algo así como 1 en 2 ^ 23, lo que significa que necesitaría un número ridículo de pruebas. Probablemente desee unos cuantos órdenes de magnitud más que el número de muestras iniciales (2 ^ 53). Sin embargo, no puede ser perfectamente uniforme si el multiplicador no divide equitativamente el número de muestras, razón por la cual Arnauld usa una potencia de dos.
Martin Ender
4

Bash (+ coreutils), 44 bytes

/ dev / solución basada en urandom

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

Leerá enteros de 32 bits sin signo /dev/urandomy los filtrará awkhasta que encuentre uno dentro de un rango determinado, luego sed qabortará la tubería.

zepelín
fuente
¡Hurra por bash :)
4

Haskell, 70 bytes

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

No es un algoritmo muy eficiente pero funciona. Genera una lista infinita de enteros (o flotantes si es necesario, debido al sistema de tipos de Haskell) delimitada por [0,2 ^ 30] y toma el primero menor o igual que n. Para pequeños n esto puede llevar mucho tiempo. Los números aleatorios deben distribuirse uniformemente, como se especifica en la documentación para randomR lo que todos los números en el intervalo [0,2 ^ 30] deben tener la misma probabilidad (1 / (2 ^ 30 + 1)), por lo tanto, todos los números en [ 0, n] tienen la misma probabilidad.

Versión alternativa:

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

Esta versión es terrible pero ahorra un byte completo. randomsusa un rango arbitrario definido por el tipo para generar una lista infinita de números. Esto puede incluir absaspectos negativos, por lo que debemos mapearlo para forzarlos a ser positivos (o cero). Esto es extremadamente lento para cualquier valor de n que no sea absurdamente grande. EDITAR : Me di cuenta más tarde de que esta versión no está distribuida uniformemente porque la probabilidad de obtener 0 es peor que los otros números debido al uso de abs. Para producir algún número, mel generador podría producir mo, -mpero en el caso de 0, solo 0 funcionará, por lo tanto, su probabilidad es la mitad de los otros números.

usuario1472751
fuente
¡Hurra por Haskell (también)!
4

Jalea , 9 bytes

⁴!Ẋ’>Ðḟ⁸Ṫ

Pruébalo en línea!- ¡el código anterior no se ejecutará en TIO desde un rango de tamaño 16! debe construirse primero (¡sin mencionar el hecho de que luego deben barajarse y luego filtrarse!), por lo que esto es lo mismo en una escala mucho más pequeña, repetido 30 veces para una entrada de 3 con un límite de 10.

¿Cómo?

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

Nota: sería más de mil veces más eficiente para el mismo recuento de bytes si ȷ⁵hiciera lo que uno esperaría ingenuamente y devolvería diez a diez, pero ese no es el caso ya que no se evalúa como un diez literal para ser utilizado por el número literal, ȷ...sino que se analizan dos literales separados, ȷcon su exponente predeterminado de tres dando mil y diez.

Jonathan Allan
fuente
Eh, eso es 9 caracteres, pero 22 bytes
Kristoffer Sall-Storgaard
@ KristofferSall-Storgaard Cada carácter es uno de los 256 bytes en la página de códigos de Jelly , olvidé hacer que la palabra bytes sea un enlace como lo hago habitualmente.
Jonathan Allan
1
año, lo busqué y descubrí lo mismo
Kristoffer Sall-Storgaard
4

JDK 9 en jshell, 75 59 bytes

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

Uso

((IntFunction)(n->(new Random()).ints(0,1<<30).dropWhile(x->x>n).findAny())).apply(<n>)
  • -16 bytes: ¡Gracias Jakob!
  • Asume que consideramos que jshell es un entorno de tiempo de ejecución válido.
  • jshell en sí mismo, como entorno de tiempo de ejecución, no requiere importaciones explícitas para las bibliotecas principales y no requiere punto y coma.
  • Devuelve un OptionalInt . Las reglas no especifican que el tipo de retorno debe ser primitivo y considero OptionalIntque es una representación válida del resultado.
Pete Terlep
fuente
1
Gracias a @ kevin-cruijssen por la inspiración. Mi primer código de golf!
Pete Terlep
Si se acepta o no la salida en caja es diferente de si Optionalse acepta o no. Confirmaría con el póster si fuera usted. Además, no es necesario contar toda la tarea; solo la expresión lambda es suficiente.
Jakob
1
Puede guardar 4 bytes eliminando paréntesis alrededor del parámetro lambda ny new Random().
Jakob
3

PHP, 30 bytes

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

Corre con echo <N> | php -Rn '<code>'.

elige un número aleatorio entre 0 y getrandmax() (2 ** 31-1 en mi máquina de 64 bits);
se repite mientras que es más grande que la entrada.

Esta puede tomar un tiempo ... mi AMD C-50 (1 GHz) necesitó entre 0.3 y 130 segundos para N=15.

Una forma más rápida para el promedio N( 46 bytes ):

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

o

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

toma N+1 enteros aleatorios, los resume y toma el módulo con N+1.
El C-50 necesita aprox. 8 segundos para 1 millón de carreras.

Una solución no válida para 19 bytes :

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

PowerShell , 35 bytes

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

Pruébalo en línea!

Otro método de muestreo de rechazo. Este es un forbucle infinito , que establece el valor de $aser un Randomnúmero entero entre 0y 1gb( = 1073741824 = 2^30), y se mantiene en bucle siempre y cuando ese entero sea -greatro a tla entrada$args . Una vez que se completa el ciclo, simplemente ponemos $aen la tubería y la salida es implícita.

Nota: Esto llevará mucho tiempo si la entrada es un número pequeño.

AdmBorkBork
fuente
3

Python 2 , 72 69 bytes

-3 bytes gracias a xnor (anular el idincorporado como una variable)

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

Pruébalo en línea!

randrange(2**30)produce un número distribuido pseudo-uniformemente (Mersenne Twister 2 19937-1 ) del rango [0,2 30 ) . Como nse garantiza que está por debajo de 2 30, esto simplemente se puede llamar repetidamente hasta que no sea mayor que la entrada. Tomará un tiempo esperado largo para valores muy bajos de n, pero generalmente funciona en un minuto incluso para entradas tan bajas como 50.

Jonathan Allan
fuente
2
Puede inicializar r=''como "infinito". O, mejor aún, no inicialice ry en su lugar use en idtodas partes r.
xnor
2

05AB1E , 11 bytes

žIÝ.rDI›_Ϥ

Pruébalo en línea!

Explicación

ž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

Como la lista [0 ... 2147483648]es demasiado grande para TIO, el enlace usa1.000.000 lugar.

Solución alternativa (en promedio) mucho más rápida de 11 bytes

[žIÝ.RD¹›_#

Pruébalo en línea

Explicación

[             # 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
fuente
žJL.R%para 6 a menos que me falte algo enorme. Presione 2 ^ 32, lista de 0 a 2 ^ 32, selección aleatoria. Módulo de entrada. Absolutamente arruinará la eficiencia que tiene.
Magic Octopus Urn
@ carusocomputing. Necesitaría un valor Ide 7 bytes para obtener los argumentos del módulo en el orden correcto (y tal Ývez en lugar de L), pero de lo contrario, esa es ciertamente una solución más corta. Vi a Dennis haciendo eso en su respuesta de Jelly, pero como esta fue mi primera idea, me quedé con esto. Como ese enfoque es diferente de esto, podría publicarlo como una respuesta separada.
Emigna
DI‹ÏEvitaría el bucle.
Magic Octopus Urn
Además, tal como está, no se garantiza que esto termine; Si no me equivoco, una entrada de 0casi siempre daría como resultado un bucle casi infinito, lo que dificulta la terminación. Aunque la solución permite la posibilidad de terminar en todos los escenarios, no está garantizada debido a la aleatoriedad.
Magic Octopus Urn
@carusocomputing: para una entrada muy pequeña, la segunda versión, en promedio, tardaría mucho tiempo en terminar, sí, pero con el tiempo suficiente lo haría.
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]

Explicación

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.

Esto es muy ineficiente, ya que crea 2 ^ 31 enteros, los baraja y los filtra.

No veo ningún punto en compartir un enlace TIO, donde está creando listas tan grandes, así que aquí hay un enlace TIO para n = 100.

Pruébalo en línea!

Yytsi
fuente
2

Java 8, 84 83 80 71 62 bytes

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

-1 byte gracias a @ OliverGrégoire .
-3 bytes gracias a @Jakob .
-9 bytes convirtiendo Java 7 a Java 8.
-9 bytes cambiando java.util.Random().nextInt(1<<30)a(int)(Math.random()*(1<<30)) .

Explicación:

Pruébalo aquí

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

NOTA: Obviamente, puede tomar mucho tiempo para entradas pequeñas.

Salida de ejemplo:

407594936
Kevin Cruijssen
fuente
2
@ Aaron también cuestioné esto, pero veo el segundo punto: "Cualquier argumento al llamar a una función incorporada o aleatoria de la biblioteca debe ser constante. Es decir, deben ser completamente independientes del valor de entrada". Esta es la razón por la que se usa max int.
Poke
1
2^30= 1073741824. Preferiste usar -1>>>1(= 2147483647). Pero esto existe: 1<<30que es exactamente igual a 2^30; y es 1 byte más corto.
Olivier Grégoire
1
¿Qué tal int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}?
Jakob
@ Jakob Gracias. Incluso lo acorté en 18 bytes más usando Java 8 en lugar de 7, y usando en Math.random()lugar de java.util.Random().nextInt.
Kevin Cruijssen
2

Python 3, 51 bytes

Aquí hay una solución de Python con una fuente aleatoria poco ortodoxa.

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

Pruébalo en línea!

Entonces, para romper esto.

int(input())+1

Obtiene el número de entrada y lo agrega 1.

set(range(...))

Crea el conjunto {0, 1, 2, 3, 4, ... n}para todos los resultados posibles.

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

Toma el conjunto, lo convierte en una lista y toma el primer elemento.

Esto funciona porque en Python 3, PYTHONHASHSEEDset() establece el orden de ( no se puede obtener, pero se establece en la ejecución del script).

Es cierto que supongo que esta es una distribución uniforme, ya que el hash()valor se asigna aleatoriamente y estoy buscando elegir aleatoriamente el valor con un valor específico hash(), en lugar de simplemente devolverlo hash(input()).

Si alguien sabe si esta es una distribución uniforme, o cómo podría probarla, por favor comente.

El mate
fuente
1

C #, 57 bytes

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

Función anónima que devuelve un número entero entre 0 yn inclusive.

Cuanto menor sea el número de entrada, mayor será el tiempo para devolver un valor aleatorio.

Programa completo:

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
fuente
2
"Cualquier argumento al llamar a una función aleatoria integrada o de biblioteca debe ser constante. Es decir, deben ser completamente independientes del valor de entrada". El argumento para Nextno es estático.
Yytsi
1

Bash + coreutils, 20 bytes

Golfed

seq 0 $ 1 | shuf | sed 1q

shuf: genera permutaciones aleatorias

Shuf usará el siguiente código : para generar permutaciones:

permutation = randperm_new (randint_source, head_lines, n_lines);

que termina en 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.  */
      ...
}

que, a su vez, leerá algunos bytes de los datos aleatorios de la fuente de aleatoriedad de bajo nivel:

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

es decir, en el nivel bajo, no existe una dependencia directa entre el shufvalor de entrada y los datos leídos de la fuente de aleatoriedad (aparte de calcular la capacidad de memoria intermedia de bytes requerida).

zepelín
fuente
66
¿No es esto dar la entrada como argumento para su generador de números aleatorios?
Martin Ender
Incluso si esto no es válido, envíe otra respuesta bash.
@MartinEnder bien, no directamente, solo usa la entrada para definir el límite superior para el rango entero generado y jot will arrange for all the values in the range to appear in the output with an equal probability(eso es probablemente límite, pero aún así).
zepelín
2
Si profundizo lo suficiente en cualquier generador de números aleatorios, estoy seguro de que encontraré una llamada en un RNG de nivel inferior que no utiliza directamente el argumento original. El objetivo del desafío es obtener una distribución uniforme de tamaño arbitrario a partir de una distribución de tamaño fijo, que todavía no está haciendo.
Martin Ender
1

SmileBASIC, 38 bytes

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

Genera números aleatorios hasta que obtiene uno que es más pequeño que la entrada.

12Me21
fuente
1

Ruby, 23 15 23 32 29 bytes

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

Cómo funciona:

  • 1while [...]; ejecuta la declaración al menos una vez: 1 anteswhile actúa como un nop
  • Obtenga un número aleatorio en el rango 0..2 ^ 30-1 ( inferior a 2 ^ 30 , como se especifica)
  • Repita si el número es mayor que el parámetro de entrada (podría tomar algún tiempo cuando n es pequeño)
GB
fuente
1

Ohmios, 26 bytes

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

Explicación:

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
fuente
¿Hay un intérprete para este idioma? ¿Y qué hay de la página de códigos?
ATaco
@ATaco: Intérprete , página de códigos: 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}

Muestreo de rechazo simple.

Nota: dado que la semilla de matemáticas / rand es una constante 1, la persona que llama debe sembrar a menos que se desee un resultado constante.

Prueba: https://play.golang.org/p/FBB4LKXo1r Ya no es prácticamente comprobable en un sistema de 64 bits, ya que devuelve una aleatoriedad de 64 bits y utiliza pruebas de rechazo.

package main

import "fmt"
import "time"

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

func main() {
    Seed(time.Now().Unix())
    fmt.Println(R(1073741823))
}
Riking
fuente
1
si lo usa import."math/rand", Int31está disponible en el espacio de nombres global y puede guardar 4 bytes, también intse garantiza que tenga al menos 32 bits, lo que le ahorrará otros 6 bytes
Kristoffer Sall-Storgaard
Utilice la :=sintaxis para otros 3 bytes
Kristoffer Sall-Storgaard el
El uso de int en lugar de int32 no guarda ningún byte ya que necesitamos convertir el resultado de Int31 () - 3 * int + () = 11 bytes versus 2 * int32 = 10 bytes.
Riking
1
No es necesario lanzar, hay una Int()función en el paquete de rand, también, puede eliminar el espacio después deimport
Kristoffer Sall-Storgaard