Tarefa
Dado um número inteiro positivo n
menor que o 2^30
especificado como entrada da maneira que você escolher, seu código deve gerar um número inteiro aleatório entre 0
e n
, inclusive. O número que você gerar deve ser escolhido de maneira uniforme e aleatória . Cada valor de 0
a n
deve ocorrer com a mesma probabilidade (consulte Regras e Advertências).
Regras e Advertências
Seu código pode assumir que qualquer gerador de números aleatórios incorporado à sua linguagem ou biblioteca padrão que afirma ser aleatoriamente uniforme é de fato uniforme. Ou seja, você não precisa se preocupar com a qualidade da fonte aleatória que está usando. Contudo,
- Você precisa estabelecer que, se a fonte aleatória que você está usando é uniforme, seu código gera corretamente um número inteiro aleatório uniforme de
0
paran
. - Qualquer argumento ao chamar uma função aleatória interna ou de biblioteca deve ser constante. Ou seja, eles devem ser completamente independentes do valor de entrada.
- Seu código pode terminar com probabilidade 1, em vez de ser garantido.
Notas
randInt(0,n)
não é válido, pois leva a entrada como argumento para uma função interna ou de biblioteca.rand()%n
vai não dar um número aleatório uniforme em geral. Como exemplo dado pela betseg, ifintmax == 15
en = 10
, então você terá muito mais chances de obter0-5
que6-10
.floor(randomfloat()*(n+1))
também não fornecerá um número aleatório uniforme em geral devido ao número finito de diferentes valores possíveis de ponto flutuante entre 0 e 1.
code-golf
number
random
probability-theory
totalmente humano
fonte
fonte
rng()
fornece0
-100
sen = 75
, e função érng()%75
, em seguida, 0-25 será mais comum ...)Respostas:
máquinas x86 com
rdrand
instrução, 10 bytesCódigo da máquina
A entrada está no registrador
rdi
e a saída está emrax
.Isso respeita o SYS V AMD64 ABI, para que o código efetivamente implemente uma função C
com entradas de 32 bits.
A instrução
rdrand
é descrita pela IntelAo lidar com o CSRNG, está implícito que a distribuição é uniforme, de qualquer maneira, citando o NIST SP 800-90A:
O procedimento gera um número aleatório e, se não for estritamente maior que a entrada, será retornado.
Caso contrário, o processo é reiterado.
Como
eax
é de 32 bits,rdrand
retorna um número entre 0 e 2 32 -1; portanto, para cada n em [0, 2 32 -1], o número de iterações esperadas é 2 32 / (n + 1), definido para todos os n em [0, 2 30 ).fonte
jnc
?rdrand
define oCF
iif se os dados retornados forem válidos. Os dados podem ser inválidos porque muitas solicitações esgotaram o conjunto de entropia. Veja a entrada manual para rdrand e isso .Geléia ,
76 bytesGraças a @ JonathanAllan por jogar fora um byte!
Não pode ser executado no TIO porque (16!)! é um número enorme .
Como funciona
fonte
Mathematica, 29 bytes
Baseado na resposta da geléia de Dennis .
Eu não recomendaria realmente executar isso.
2e9!
é um número bastante grande ...É mais curto gerar um número enorme que é divisível por todas as entradas possíveis e mapear o resultado para o intervalo necessário com um módulo simples.
Amostragem de rejeição, 34 bytes
Minha antiga abordagem que levou a um código um pouco mais interessante:
Amostragem básica de rejeição. Inicializamos a saída para 13! (que é maior que a entrada máxima 2 30 ) e substitua-a repetidamente por um número inteiro aleatório entre 0 e 13! desde que o valor seja maior que a entrada.
fonte
Braquilog , 9 bytes
Experimente online!
Isso usa
13!
como na resposta de Martin Ender (13ḟ
é um byte a menos que2^₃₀
).ṙ
é implementado usandorandom_between/3
, que, ao cavar sua fonte, usa orandom_float/0
qual está vinculado aorandom/1
qual usa o algoritmo Mersenne Twister, que é uniforme para nossos propósitos.Explicação
fonte
Prolog (SWI) , 38 bytes
Trabalhos por amostragem por rejeição.
Gere um número aleatório entre 0 e 2 ^ 31-1 = 2147483647 até que um menor ou igual à entrada seja encontrado.
Sinto como se eu pudesse usar um corte em vez do outro, mas não consigo ver como.
fonte
repeat
, mas acaba sendo 3 bytes mais longo ... Não sei se há uma maneira mais curta de ter pontos de escolha infinitos do que repetir.,!.
para forçar um retorno, mas ou estou lembrando errado ou não é aplicável a esta solução.Labirinto , 63 bytes
(Agradecemos a @MartinEnder por ajuda com alguns esportes pesados aqui.)
O labirinto é uma linguagem 2D e sua única fonte de aleatoriedade está em uma situação como a seguinte:
Suponha que o ponteiro de instruções esteja no
x
e movendo-se para baixo. Em seguida, ele pousa no<
, que, se o topo da pilha for 0 (o que é sempre o caso no programa real acima), desloca a linha atual deixada por 1:O ponteiro de instruções está agora se
<
movendo para baixo. Em uma junção, o labirinto gira com base no topo da pilha - negativo é virar à esquerda, positivo é virar à direita e zero é avançar. Se o topo da pilha ainda for zero neste momento, não podemos avançar ou retroceder, pois não há caminho, portanto, o Labyrinth irá aleatoriamente entre virar à esquerda ou virar à direita com igual probabilidade.Essencialmente, o que o programa acima faz é usar o recurso de aleatoriedade para gerar números de 100 bits (100 especificados por
#00
aqui) e continuar fazendo um loop até gerar um número<= n
.Para o teste, provavelmente será útil usar
#0"
números de 10 bits, sendo o"
caminho não operacional. Experimente online!Explicação aproximada:
fonte
Python, 61 bytes
Edit: Atualizado para evitar o formulário proibido
Edit2: salvou 2 bytes, obrigado @ JonathanAllan
Edit3: Pago 2 bytes por uma solução totalmente funcional - obrigado novamente @ JonathanAllan
Edit4: Removido
f=
, economizando 2 bytesEdit5: economizou mais 1 byte graças a @ JonathanAllan
Edit6: salvou mais 2 bytes graças a @ JonathanAllan
A essa altura, a culpa seria apontada para mim pelas coisas ruins e JonathanAllan pelas coisas que ajudam.
Edit7: Quando chove, derrama - outros 2 bytes
Edit8: E mais 2 bytes
fonte
n
, mas você pode salvar dois bytes ao corrigi-lo usandofrom random import*
e soltando or.
....*(-~n*1.0/2**30))
, em vez de...*((n+1)*1.0/2**30))
randrange
parece aceitar um carro alegórico, entãolambda n,x=2.**30:int(randrange(x)*-~n/x)
salva outros dois [edit]]!Python 2 , 61 bytes
Pseudo-aleatoriamente escolhe números inteiros entre 0 e k para todos os valores de k entre 0 e 2 31 de - 2 , em seguida, converte o número inteiro que corresponde a k = n .
fonte
Lote, 64 bytes
%random%
só dá 15 bits de aleatoriedade, então eu tenho que combinar dois números aleatórios. Loops até que o valor aleatório esteja dentro do intervalo desejado, então é lento para baixon
; 98 bytes para uma versão mais rápida:fonte
n
?call
, invocar um script em lotes encerra o script atual.MATL , 12 bytes
Agradecemos a @AdmBorkBork e a @Suever por me dizerem como desativar o cache TIO.
Experimente online! .
Isso usa um método de rejeição : gere um número inteiro aleatório de
0
para2^30-1
e repita enquanto excede a entradan
. É garantido que ele termine com probabilidade1
, mas o número médio de iterações é2^30/n
e, portanto, leva muito tempo paran
significativamente menor que2^30
.fonte
JavaScript (ES6),
5554 bytesGera números inteiros no intervalo [0 ... 2 k - 1] , onde k é o menor número inteiro, de modo que 2 k é maior que n . Repete-se até o resultado cair em [0 ... n] .
Por quê?
Isso se baseia nas seguintes suposições:
Internamente, os valores inteiros pseudo-aleatórios gerados pelo mecanismo JS para alimentar
Math.random()
são uniformes em qualquer intervalo [0 ... 2 k -1] (com k <32 ).Uma vez multiplicados por uma potência exata de 2, os valores flutuantes IEEE 754 retornados por
Math.random()
ainda são uniformes nesses intervalos.Se alguém puder confirmar ou refutar essas hipóteses, informe-me nos comentários.
Demo
Gera 1 milhão de valores em [0 ... 2] e exibe as estatísticas do resultado.
Mostrar snippet de código
fonte
Bash (+ coreutils), 44 bytes
Solução baseada em / dev / urandom
Lerá números inteiros de 32 bits não assinados
/dev/urandom
e os filtraráawk
até encontrar um dentro de um determinado intervalo esed q
abortará o pipe.fonte
Haskell, 70 bytes
Não é um algoritmo muito eficiente, mas funciona. Ele gera uma lista infinita de números inteiros (ou flutua, se necessário, devido ao sistema de tipos de Haskell) delimitado por [0,2 ^ 30] e leva o primeiro menor ou igual a n. Para n pequeno, isso pode levar muito tempo. Os números aleatórios devem ser distribuídos uniformemente, conforme especificado na documentação para randomR, para que todos os números no intervalo [0,2 ^ 30] tenham a mesma probabilidade (1 / (2 ^ 30 + 1)), portanto, todos os números em [ 0, n] têm a mesma probabilidade.
Versão alternativa:
Esta versão é terrível, mas salva um byte inteiro.
randoms
usa um intervalo arbitrário definido pelo tipo para gerar uma lista infinita de números. Isso pode incluir negativos, por isso precisamos mapeá-loabs
para forçá-los positivos (ou zero). Isso é extremamente lento para quaisquer valores de n que não sejam absurdamente grandes. EDIT : Percebi mais tarde que esta versão não é distribuída uniformemente porque a probabilidade de obter 0 é pior que os outros números devido ao uso deabs
. Para produzir algum número,m
o gerador poderia produzirm
ou,-m
mas no caso de 0, apenas 0 funcionará, portanto sua probabilidade é metade dos outros números.fonte
Geléia , 9 bytes
Experimente online! - o código acima não será executado no TIO desde uma faixa de tamanho 16! deve ser construído primeiro (sem mencionar o fato de que eles precisam ser embaralhados e depois filtrados!); portanto, é a mesma coisa em uma escala muito menor, repetida 30 vezes para uma entrada de 3 com um limite de 10.
Quão?
Nota: seria mais de mil vezes mais eficiente para a mesma contagem de bytes se
ȷ⁵
fizesse o que seria esperado ingenuamente e retornasse dez para os dez, mas esse não é o caso, pois o⁵
não é avaliado como um dez literal a ser usado pelo número literal,ȷ...
mas dois literais separados são analisados,ȷ
com o expoente padrão de três produzindo mil e⁵
dez.fonte
JDK 9 no jshell,
7559 bytesUso
OptionalInt
. As regras não especificam que o tipo de retorno deve ser primitivo e estou considerando umaOptionalInt
representação válida do resultado.fonte
Optional
aceitação de uma. Eu confirmaria com o pôster se fosse você. Além disso, não há necessidade de contar toda a tarefa; apenas a expressão lambda é suficiente.n
enew Random()
.PHP, 30 bytes
Corra com
echo <N> | php -Rn '<code>'
.escolhe um número aleatório entre 0 e
getrandmax()
(2 ** 31-1 na minha máquina de 64 bits);repete enquanto é maior que a entrada.
Isso pode demorar um pouco ... meu AMD C-50 (1 GHz) precisou entre 0,3 e 130 segundos por
N=15
.Uma maneira mais rápida para a média
N
( 46 bytes ):ou
pega
N+1
inteiros aleatórios, resume-os e pega o módulo comN+1
.O C-50 precisa de aprox. 8 segundos para 1 milhão de execuções.
Uma solução inválida para 19 bytes :
fonte
PowerShell , 35 bytes
Experimente online!
Outro método de amostragem de rejeição. Este é um infinito
for
ciclo, definindo o valor$a
da ser umRandom
inteiro entre0
e1gb
(= 1073741824 = 2^30
), e continua looping tanto tempo quanto aquele inteiro é-g
reatert
han a entrada$args
. Uma vez concluído o loop, apenas colocamos$a
no pipeline e a saída está implícita.Nota: Isso levará muito tempo se a entrada for um número pequeno.
fonte
Python 2 ,
7269 bytes-3 bytes graças ao xnor (substitua o
id
embutido como uma variável)Experimente online!
randrange(2**30)
produz um número distribuído pseudo-uniformemente (Mersenne Twister 2 19937-1 ) a partir do intervalo [0,2 30 ) . Comon
é garantido que esteja abaixo de 2 30, isso pode ser simplesmente chamado repetidamente até que não seja maior que a entrada. Levará muito tempo para valores muito baixos den
, mas geralmente funciona dentro de um minuto, mesmo para entradas tão baixas quanto 50.fonte
r=''
como "infinito". Ou, melhor ainda, não inicializer
e use emid
qualquer lugarr
.Perl 6 , 29 bytes
Inspirado na solução Mathematica de Martin Ender .
Gera uma sequência infinita lenta de números inteiros aleatórios entre 0 e 2 ^ 30-1 e pega o primeiro que está entre 0 e a entrada.
Experimente online!
fonte
05AB1E , 11 bytes
Experimente online!
Explicação
Como a lista
[0 ... 2147483648]
é muito grande para o TIO, o link é usado1.000.000
.Solução alternativa (em média) de 11 bytes muito mais rápida
Experimente online
Explicação
fonte
žJL.R%
por 6, a menos que esteja perdendo algo enorme. Pressione 2 ^ 32, lista de 0 a 2 ^ 32, escolha aleatória. Entrada de módulo. Absolutamente estragar a eficiência que você tem.I
de 7 bytes para obter os argumentos do módulo na ordem certa (e talvez emÝ
vez deL
), mas, caso contrário, essa certamente é uma solução mais curta. Vi Dennis fazendo isso em sua resposta Jelly, mas como essa foi minha primeira ideia, guardei isso. Como essa abordagem é diferente, você pode publicá-la como uma resposta separada.DI‹Ï
evitaria o loop.0
quase sempre resultaria em um loop quase infinito, dificultando a finalização. Embora a solução permita a possibilidade de terminar em todos os cenários, ela não é garantida devido à aleatoriedade.Python 2, 89 bytes
Explicação
Isso é muito ineficiente, pois cria 2 ^ 31 números inteiros, embaralha e os filtra.
Não vejo sentido em compartilhar um link TIO, onde ele está criando listas tão grandes, então aqui está um link TIO para
n
= 100.Experimente online!
fonte
Java 8,
8483807162 bytes-1 byte graças a @ OliverGrégoire .
-3 bytes graças a @Jakob .
-9 bytes convertendo Java 7 em Java 8.
-9 bytes alterando
java.util.Random().nextInt(1<<30)
para(int)(Math.random()*(1<<30))
.Explicação:
Experimente aqui.
NOTA: Obviamente, pode demorar muito para pequenas entradas.
Exemplo de saída:
fonte
2^30
=1073741824
. Você preferiu usar-1>>>1
(=2147483647
). Mas isso existe: o1<<30
que é exatamente igual a2^30
; e é 1 byte mais curto.int c(int n){int r;for(;(r=new java.util.Random().nextInt(1<<30))>n;);return r;}
?Math.random()
vez dejava.util.Random().nextInt
.Python 3, 51 bytes
Aqui está uma solução python com uma fonte aleatória não ortodoxa.
Experimente online!
Então, para quebrar isso.
Obtém o número de entrada e adiciona
1
a ele.Cria o conjunto
{0, 1, 2, 3, 4, ... n}
para todos os resultados possíveis.Pega o conjunto, converte-o para a lista e pega o primeiro item.
Isso funciona porque no Python 3, a ordem de
set()
é estabelecida pelo PYTHONHASHSEED ( não pode ser obtida, mas é estabelecida na execução do script).É certo que estou supondo que essa seja uma distribuição uniforme, pois o
hash()
valor é atribuído aleatoriamente e estou olhando aleatoriamente para escolher o valor com um específicohash()
, em vez de apenas retornar ohash(input())
próprio.Se alguém souber se é uma distribuição uniforme ou como eu poderia testar isso, comente.
fonte
C #, 57 bytes
Função anônima que retorna um número inteiro entre 0 e n, inclusive.
Quanto menor o número de entrada, maior o tempo para retornar um valor aleatório.
Programa completo:
fonte
Next
não é estático.Bash + coreutils, 20 bytes
Golfe
seq 0 $ 1 | shuf | sed 1q
Shuf usará o seguinte código : para gerar permutações:
que acaba em
randint_genmax
que, por sua vez, lerá alguns bytes dos dados aleatórios da fonte de aleatoriedade de baixo nível:
ou seja, no nível baixo, não há dependência direta entre o
shuf
valor de entrada e os dados lidos da fonte de aleatoriedade (além de calcular a capacidade de buffer de bytes necessária).fonte
jot will arrange for all the values in the range to appear in the output with an equal probability
(isso provavelmente é limítrofe, mas ainda assim).SmileBASIC, 38 bytes
Gera números aleatórios até obter um menor que a entrada.
fonte
Ruby,
23 15 23 3229 bytesComo funciona:
1while [...];
executa a instrução pelo menos uma vez:1
beforewhile
age como um nopfonte
Ohm, 26 bytes
Explicação:
fonte
Vai,
63.61 bytesUse-o assim:
Teste ao vivo no playground
fonte
Golang,
847871 bytesAmostragem simples de rejeição.
Nota: como a semente matemática / rand é uma constante 1, o chamador deve propagar a menos que um resultado constante seja desejado.
Teste: https://play.golang.org/p/FBB4LKXo1rNão é mais praticamente testável em um sistema de 64 bits, pois está retornando a aleatoriedade de 64 bits e usando o teste de rejeição.fonte
import."math/rand"
, em seguida,Int31
está disponível no espaço global e você pode salvar 4 bytes, tambémint
é garantida para ser pelo menos 32 bits, poupando-lhe mais 6 bytes:=
a sintaxe por mais 3 bytesInt()
função no pacote rand, também, você pode remover o espaço depoisimport