Entrada: Dois números inteiros n e k, fornecidos de qualquer forma que seja conveniente para o seu código
Saída Uma sequência aleatória não decrescente de k números inteiros, cada um no intervalo de 1 a n. A amostra deve ser escolhida uniformemente entre todas as seqüências não decrescentes de k números inteiros com números inteiros no intervalo de 1 a n.
A saída pode estar em qualquer formato razoável que você achar conveniente.
Você pode usar qualquer gerador pseudo-aleatório que sua biblioteca / idioma favorito fornecer.
Podemos assumir que os números inteiros n, k> 0.
Exemplo
Diga n, k = 2. As seqüências não decrescentes são
1,1
1,2
2,2
Cada sequência deve ter probabilidade de 1/3 de ser emitida.
Restrição
Seu código deve ser executado em apenas alguns segundos para k = 20 en = 100.
O que não funciona
Se você apenas amostrar cada número inteiro aleatoriamente do intervalo de 1 a n e classificar a lista, não obterá uma distribuição uniforme.
fonte
Respostas:
Na realidade ,
1412 bytesEsta resposta é baseada na resposta 05AB1E de Emigna e as respostas sobre esta questão Math.SE . Sugestões de golfe são bem-vindas! Experimente online!
Ungolfing
fonte
Python, 89 bytes
Gerar uma sequência crescente em vez de uma não decrescente seria simples: este é apenas um subconjunto aleatório de
k
números entre1
en
, classificado.Porém, podemos converter uma sequência crescente em uma não decrescente, reduzindo cada intervalo entre números consecutivos em 1. Portanto, um intervalo de 1 se torna um intervalo de 0, formando números iguais. Para fazer isso, diminua o
i
décimo maior valor emi
Para que o resultado seja de
1
paran
, a entrada deve ser de1
paran+k-1
. Isso fornece uma bijeção entre seqüências não decrescentes de números entre1
en
, para aumentar sequências entre1
en+k-1
. A mesma bijeção é usada no argumento de estrelas e barras para contar essas seqüências.O código usa a função python
random.sample
, que coletak
amostras sem substituição da lista de entrada. A classificação fornece a sequência crescente.fonte
import*
salvar 1 byte) #05AB1E , 13 bytes
Experimente online!
Explicação
fonte
Python, 87 bytes
A probabilidade de que o valor máximo possível
n
seja incluído é igualk/(n+k-1)
. Para incluí-lo, coloque-o no final da lista e diminua os números necessários restantesk
. Para excluí-lo, diminua o limite superiorn
. Em seguida, recorra até que não sejam necessários mais valores (k==0
).O Python
random
não parece ter um built-in para uma variável Bernoulli: 1 com alguma probabilidade e 0 caso contrário. Portanto, isso verifica se um valor aleatório entre 0 e 1 gerado porrandom
cai abaixok/(n+k-1)
. Python 2 seria a razão como a divisão float, por isso, em vez se multiplicam pelo denominador:k>random()*(n+k-1)
.fonte
numpy.random
, o que é muito longo.JavaScript (Firefox 30+), 74 bytes
Explicação
A excelente resposta Python do xnor contém um resumo muito bom de como / por que a técnica usada aqui funciona. O primeiro passo é criar o intervalo [1, 2, ..., n + k - 1] :
Em seguida, precisamos pegar k itens aleatórios desse intervalo. Para fazer isso, precisamos selecionar cada item com probabilidade s / q , onde s é o número de itens ainda necessários e q é o número de itens restantes no intervalo. Como estamos usando uma compreensão de array, isso é bastante fácil:
Isso nos dá uma sequência crescente de números uniformemente distribuída . Isso pode ser corrigido subtraindo o número de itens j que encontramos anteriormente:
Finalmente, armazenando k em j , podemos incorporar
k--
na expressão e salvar alguns bytes:fonte
TI-BASIC, 54 bytes
Siga a lógica do xnor, com uma pequena ressalva. Teoricamente, podemos barbear um byte fazendo algo assim:
Mas rand (é reservado para criar uma lista de números aleatórios, portanto, não poderíamos fazer a multiplicação implícita desejada para salvar um byte.
Isso deve ser executado decentemente rápido em um 84+ por restrição, mas vou verificar se posso.
fonte
PHP,
777573 bytesExecute assim:
Explicação
Tweaks
end()
chamada e conjunto$argv[2]
para$k
, em vez de acesso encurtar a argumentos$i
cada iteraçãofonte