Expanda um intervalo aleatório de 1 a 5 a 1 a 7

692

Dada uma função que produz um número inteiro aleatório no intervalo de 1 a 5, escreva uma função que produz um número inteiro aleatório no intervalo de 1 a 7.

  1. O que é uma solução simples?
  2. O que é uma solução eficaz para reduzir o uso de memória ou executar em uma CPU mais lenta?
Roger Pate
fonte
Ele provou ser um problema inesperadamente interessante, eu ainda penso como 1) fazê-lo em tempo fixo e 2) não estragar a distribuição uniforme (se houve)
eugensk
Tivemos o mesmo problema ao escolher um jogador de 5 com um dado. Jogamos os dados em turnos, quem obtém a pontuação máxima é escolhido. A uniformidade foi achived, mas não o tempo constantness :)
eugensk
Eu seria prejudicado se eu postasse uma resposta dizendo que o problema não exige que você precise usar a função fornecida e apenas escreva uma que retorne 1-7 aleatoriamente?
Doctor Blue
Que tal 7 * rand5() / 5?
Kiwixz
@kiwixz, que produzirá "entre 1 e 7", mas você não obterá 3 ou 6: {1: 19.96, 2: 20.02, 4: 20.01, 5: 19.99, 7: 20.02} porcentagens aproximadas testando manualmente. 7 * .2, 7 * .4, 7 * .6, 7 * .8, 7 * 1.
Pythonlarry

Respostas:

572

Isso é equivalente à solução de Adam Rosenfield, mas pode ser um pouco mais claro para alguns leitores. Ele assume que rand5 () é uma função que retorna um número inteiro estatisticamente aleatório no intervalo de 1 a 5, inclusive.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Como funciona? Pense assim: imagine imprimir esse conjunto de dupla dimensão no papel, prendendo-o em um cartão de dardo e jogando dardos aleatoriamente nele. Se você atingir um valor diferente de zero, é um valor estatisticamente aleatório entre 1 e 7, pois há um número igual de valores diferentes de zero para escolher. Se você acertar um zero, continue jogando o dardo até atingir um diferente de zero. É isso que esse código está fazendo: os índices iej selecionam aleatoriamente um local no quadro de dardos e, se não obtivermos um bom resultado, continuamos jogando dardos.

Como Adam disse, isso pode durar para sempre no pior caso, mas estatisticamente o pior caso nunca acontece. :)

Rob McAfee
fonte
5
Eu entendi a lógica por trás dessa solução, mas não consigo compreender que como isso resulta em probabilidade uniforme? Alguém pode explicar a matemática?
user1071840
6
@ user1071840 - se rand5for uniforme, todas as células da valsgrade têm a mesma probabilidade de serem selecionadas. A grade contém exatamente três cópias de cada número inteiro no intervalo [1, 7], mais quatro zeros. Portanto, o fluxo "bruto" de resultados tende a uma mistura uniforme de [1, 7] valores, mais alguns zeros que ocorrem um pouco mais frequentemente do que qualquer valor permitido individual. Mas isso não importa, porque os zeros são eliminados, deixando apenas uma mistura uniforme de [1, 7] valores.
Daniel Earwicker
3
A maneira de atalho para perceber o problema com isso: se você estiver chamando rand5 () apenas uma vez, terá apenas 5 resultados possíveis. Obviamente, não há como transformar isso em mais de 5 resultados possíveis sem adicionar mais aleatoriedade.
Daniel Earwicker
1
A versão mais longa: rand5 () pode ter apenas os valores (1, 2, 3, 4, 5). Portanto, rand5 () * 5 pode ter apenas os valores (5, 10, 15, 20, 25), que não são iguais a um intervalo completo (1 ... 25). Se o fizesse, subtrair 4 seria suficiente (-3 ... 21), mas nesse caso se tornará (1, 6, 11, 16, 21), portanto os pontos finais estão corretos, mas existem quatro grandes buracos: ( 2..5), (7..10), (12..15), (17..21). Finalmente, você mod 7 e adiciona 1, dando (2, 7, 5, 3, 1). Portanto, nem 4 nem 6 ocorrem. Mas (veja o atalho acima), sabíamos que só poderia haver 5 números no intervalo resultante o tempo todo, portanto havia duas lacunas.
precisa
1
Ah, porque só temos rand5 (), não RAND2 () :-)
gzak
352

Não existe uma solução (exatamente correta) que funcione em uma quantidade constante de tempo, já que 1/7 é um decimal infinito na base 5. Uma solução simples seria usar a amostragem por rejeição, por exemplo:


int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

Isso tem um tempo de execução esperado de 25/21 = 1,19 iterações do loop, mas há uma probabilidade infinitesimalmente pequena de loop para sempre.

Adam Rosenfield
fonte
7
a -1 não é necessário se a> 21 é virado para> 26 b / c não importa onde i é inferior mapas obrigado a,
BCS
26
Minha opinião sobre como explicar por que isso está correto: diga que quero escrever um programa que produz um fluxo de números aleatórios uniformes de 1 a 25; por isso eu retornaria 5 * (rand5 () - 1) + rand5 () como no código da resposta. Agora, se eu quiser construir um fluxo de números aleatórios uniformes entre 1 e 21, se eu apenas usar o primeiro fluxo, mas filtrá-lo para que os números em [22, 25] sejam rejeitados, também posso construir esse fluxo. A seguir, se eu pegar esse fluxo e filtrá-lo para que, para cada elemento x eu produza x% 7 + 1, eu tenha um fluxo de números aleatórios uniformes de 1 a 7! Muito simples, não é? : D
Paggas
6
E você está certo de que tudo se resume a se você deseja uma distribuição perfeita com o pior tempo de execução ilimitado ou uma distribuição imperfeita com um tempo de execução limitado. Isso é uma conseqüência do fato de que todas as potências 5 não são divisíveis por 7, ou equivalentemente, se você tiver 5 ^ n igualmente provavelmente seqüências de comprimento n, não há como atribuir a cada sequência um número de 1 a 7, de modo que cada um 1..7 é igualmente provável.
Adam Rosenfield
5
@Jules Olléon: Suponha que houvesse uma solução em execução em tempo constante que garantisse não fazer mais do que Nchamadas rand5()no pior dos casos. Em seguida, existem 5 ^ N resultados possíveis da sequência de chamadas para rand5, cada uma com uma saída de 1-7. Portanto, se você adicionar todas as sequências possíveis de chamadas cuja saída é kpara cada 1≤k≤7, a probabilidade de que a saída seja ké m / 5 ^ N, onde m é o número dessas seqüências. Portanto, m / 5 ^ N = 1/7, mas não há soluções inteiras possíveis (N, m) para essa ==> contradição.
Adam Rosenfield 30/01
4
@paxdiablo: Você está incorreto. A chance de um RNG verdadeiro gerar uma sequência infinita de 5's é exatamente 0, usando um raciocínio semelhante ao fato de que jogar uma moeda um número infinito de vezes é garantido para não gerar um número infinito de cabeças consecutivas . Isso também significa que a chance desse código repetir para sempre é exatamente 0 (embora exista uma chance positiva de repetir para qualquer número arbitrário de iterações).
BlueRaja - Danny Pflughoeft
153

Gostaria de adicionar outra resposta, além da minha primeira resposta . Essa resposta tenta minimizar o número de chamadas rand5()por chamada rand7()para maximizar o uso da aleatoriedade. Ou seja, se você considera a aleatoriedade um recurso precioso, queremos usar o máximo possível, sem jogar fora nenhum bit aleatório. Essa resposta também tem algumas semelhanças com a lógica apresentada na resposta de Ivan .

A entropia de uma variável aleatória é uma quantidade bem definida. Para uma variável aleatória que assume N estados com probabilidades iguais (uma distribuição uniforme), a entropia é log 2 N. Assim, rand5()possui aproximadamente 2,332193 bits de entropia e rand7()cerca de 2,80735 bits de entropia. Se esperamos maximizar nosso uso da aleatoriedade, precisamos usar todos os 2,332193 bits de entropia de cada chamada para rand5()e aplicá-los na geração de 2,80735 bits de entropia necessários para cada chamada rand7(). O limite fundamental, então, é que não podemos fazer melhor do que log (7) / log (5) = 1,20906 chamadas para rand5()por chamada rand7().

Notas laterais: todos os logaritmos nesta resposta serão da base 2, a menos que seja especificado o contrário. rand5()será assumido como retornando números no intervalo [0, 4] e rand7()assumido como retornando números no intervalo [0, 6]. Ajustar os intervalos para [1, 5] e [1, 7] respectivamente é trivial.

Então, como fazemos isso? Geramos um número real aleatório infinitamente preciso entre 0 e 1 (finja no momento que poderíamos realmente computar e armazenar um número infinitamente preciso - resolveremos isso mais tarde). Podemos gerar esse número gerando seus dígitos na base 5: escolhemos o número aleatório 0. a1 a2 a3 ..., em que cada dígito ai é escolhido por uma chamada para rand5(). Por exemplo, se nosso RNG escolheu a i= 1 para todos i, ignorando o fato de que isso não é muito aleatório, isso corresponderia ao número real 1/5 + 1/5 2 + 1/5 3 + ... = 1/4 (soma de uma série geométrica).

Ok, escolhemos um número real aleatório entre 0 e 1. Agora, afirmo que esse número aleatório é distribuído uniformemente. Intuitivamente, isso é fácil de entender, já que cada dígito foi escolhido de maneira uniforme e o número é infinitamente preciso. No entanto, uma prova formal disso é um pouco mais envolvida, já que agora estamos lidando com uma distribuição contínua em vez de uma distribuição discreta, por isso precisamos provar que a probabilidade de que nosso número esteja em um intervalo [ a, b] é igual à duração de esse intervalo b - a,. A prova é deixada como um exercício para o leitor =).

Agora que temos um número real aleatório selecionado uniformemente no intervalo [0, 1], precisamos convertê-lo em uma série de números aleatórios uniformemente no intervalo [0, 6] para gerar a saída de rand7(). Como vamos fazer isso? Exatamente o inverso do que acabamos de fazer - nós o convertemos em um decimal infinitamente preciso na base 7, e então cada dígito da base 7 corresponderá a uma saída de rand7().

Tomando o exemplo anterior, se rand5()produz um fluxo infinito de 1's, então nosso número real aleatório será 1/4. Convertendo 1/4 para a base 7, obtemos o decimal infinito 0,15151515 ..., portanto, produziremos como saída 1, 5, 1, 5, 1, 5, etc.

Ok, então temos a idéia principal, mas ainda temos dois problemas: não podemos computar ou armazenar um número real infinitamente preciso; então, como lidamos com apenas uma parte finita dele? Em segundo lugar, como realmente o convertemos para a base 7?

Uma maneira de converter um número entre 0 e 1 na base 7 é a seguinte:

  1. Multiplique por 7
  2. A parte integrante do resultado é o próximo dígito base 7
  3. Subtraia a parte integral, deixando apenas a parte fracionária
  4. Vá para a etapa 1

Para lidar com o problema da precisão infinita, calculamos um resultado parcial e também armazenamos um limite superior sobre o que poderia ser o resultado. Ou seja, suponha que tenhamos chamado rand5()duas vezes e retornou 1 nas duas vezes. O número que geramos até agora é 0,11 (base 5). Qualquer que seja o restante da série infinita de chamadas a rand5()produzir, o número real aleatório que estamos gerando nunca será maior que 0,12: é sempre verdade que 0,11 ≤ 0,11xyz ... <0,12.

Portanto, acompanhando o número atual até o momento e o valor máximo que ele poderia ter, convertemos os dois números na base 7. Se eles concordarem com os primeiros kdígitos, podemos gerar com segurança os próximos kdígitos - independentemente do que fluxo infinito de 5 dígitos da base, eles nunca afetarão a próximak dígitos da representação da base 7!

E esse é o algoritmo - para gerar a próxima saída de rand7(), geramos apenas quantos dígitos rand5()precisamos para garantir que sabemos com certeza o valor do próximo dígito na conversão do número real aleatório em base 7. Aqui está uma implementação Python, com um equipamento de teste:

import random

rand5_calls = 0
def rand5():
    global rand5_calls
    rand5_calls += 1
    return random.randint(0, 4)

def rand7_gen():
    state = 0
    pow5 = 1
    pow7 = 7
    while True:
        if state / pow5 == (state + pow7) / pow5:
            result = state / pow5
            state = (state - result * pow5) * 7
            pow7 *= 7
            yield result
        else:
            state = 5 * state + pow7 * rand5()
            pow5 *= 5

if __name__ == '__main__':
    r7 = rand7_gen()
    N = 10000
    x = list(next(r7) for i in range(N))
    distr = [x.count(i) for i in range(7)]
    expmean = N / 7.0
    expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))

    print '%d TRIALS' % N
    print 'Expected mean: %.1f' % expmean
    print 'Expected standard deviation: %.1f' % expstddev
    print
    print 'DISTRIBUTION:'
    for i in range(7):
        print '%d: %d   (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
    print
    print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)

Observe que rand7_gen()retorna um gerador, pois possui um estado interno que envolve a conversão do número em base 7. O chicote de teste chamanext(r7) 10000 vezes para produzir 10000 números aleatórios e mede sua distribuição. Somente matemática inteira é usada, portanto os resultados estão exatamente corretos.

Observe também que os números aqui ficam muito grandes, muito rápidos. Poderes de 5 e 7 crescem rapidamente. Portanto, o desempenho começará a diminuir visivelmente após a geração de muitos números aleatórios, devido à aritmética do bignum. Mas lembre-se aqui, meu objetivo era maximizar o uso de bits aleatórios, não maximizar o desempenho (embora esse seja um objetivo secundário).

Em uma execução, fiz 12091 chamadas rand5()para 10000 chamadas pararand7() , atingindo o mínimo de chamadas log (7) / log (5) em média para 4 números significativos, e a saída resultante foi uniforme.

Para portar esse código para um idioma que não tenha inteiros arbitrariamente grandes incorporados, você deverá limitar os valores pow5e pow7o valor máximo do seu tipo integral nativo - se eles ficarem muito grandes, redefina tudo e começar de novo. Isso aumentará o número médio de chamadas rand5()por chamada para rand7()um pouco, mas espero que não aumente muito, mesmo para números inteiros de 32 ou 64 bits.

Adam Rosenfield
fonte
7
+1 para uma resposta realmente interessante. Seria possível, em vez de redefinir em um determinado valor, simplesmente desligar os bits que foram usados ​​e mover os outros bits para cima, e basicamente manter apenas os bits que serão usados? Ou eu estou esquecendo de alguma coisa?
21711 Chris Lutz
1
Não tenho 100% de certeza, mas acredito que, se você fizesse isso, distorceria a distribuição levemente (embora eu duvide que essa distorção seria mensurável sem trilhões de tentativas).
Adam Rosenfield
FTW! Tentei fazer os bignums menores, mas isso não pode ser feito porque nenhuma potência de 5 tem fatores em comum com uma potência de 7! Além disso, bom uso da palavra-chave yield. Muito bem feito.
Eyal
2
Muito agradável! Podemos reter a entropia extra sem aumentar o estado? O truque é perceber que os limites superior e inferior são sempre números racionais. Podemos adicionar, subtrair e multiplicá-los sem perder a precisão. Se fizermos tudo na base 35, estamos quase lá. O restante (multiplicando por sete e retendo a parte fracionária) é deixado como exercício.
Ian
@adam Você deve consultar "limitar os valores de pow5 e pow7 ao valor máximo do seu tipo integral nativo". Em segundo lugar, você acredita que isso distorcerá a distribuição, pelo menos se for feito ingenuamente.
catalisador
36

(Eu roubei a resposta de Adam Rosenfeld e a fiz rodar cerca de 7% mais rápido.)

Suponha que rand5 () retorne um de {0,1,2,3,4} com distribuição igual e a meta seja retornar {0,1,2,3,4,5,6} com distribuição igual.

int rand7() {
  i = 5 * rand5() + rand5();
  max = 25;
  //i is uniform among {0 ... max-1}
  while(i < max%7) {
    //i is uniform among {0 ... (max%7 - 1)}
    i *= 5;
    i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
    max %= 7;
    max *= 5; //once again, i is uniform among {0 ... max-1}
  }
  return(i%7);
}

Estamos acompanhando o maior valor que o loop pode gerar na variável max . Se o resultado até agora estiver entre max% 7 e max-1, o resultado será distribuído uniformemente nesse intervalo. Caso contrário, usamos o restante, que é aleatório entre 0 e max% 7-1, e outra chamada para rand () para criar um novo número e um novo máximo. Então começamos novamente.

Edit: Espere o número de vezes para chamar rand5 () é x nesta equação:

x =  2     * 21/25
   + 3     *  4/25 * 14/20
   + 4     *  4/25 *  6/20 * 28/30
   + 5     *  4/25 *  6/20 *  2/30 * 7/10
   + 6     *  4/25 *  6/20 *  2/30 * 3/10 * 14/15
   + (6+x) *  4/25 *  6/20 *  2/30 * 3/10 *  1/15
x = about 2.21 calls to rand5()
Eyal
fonte
2
Resultados catalogados em 1.000.000 tentativas: 1 = 47216; 2 = 127444; 3 = 141407; 4 = 221453; 5 = 127479; 6 = 167536; 7 = 167465. Como você pode ver, a distribuição está faltando em relação às chances de conseguir a 1.
Robert K
2
@ The Wicked Flea: Eu acho que você está enganado. Você tem certeza de que a entrada rand5 () usada no teste produziu 0-4 em vez de 1-5, conforme especificado nesta solução?
23811 Adam Rosenfield
5
adicionar números distribuídos uniformemente não resulta em um número distribuído uniformemente. De fato, você só precisa somar 6 variáveis ​​distribuídas uniformemente para obter uma aproximação razoável de uma distribuição normal.
Mitch Wheat
2
@MitchWheat - A adição de dois números inteiros distribuídos uniformemente resulta em um número inteiro aleatório distribuído uniformemente, desde que cada soma possível possa ser gerada exatamente de uma maneira. Esse é o caso da expressão 5 * rand5() + rand5().
Ted Hopp
28

Algoritmo:

7 pode ser representado em uma sequência de 3 bits

Use rand (5) para preencher aleatoriamente cada bit com 0 ou 1.
Por exemplo: chame rand (5) e

se o resultado for 1 ou 2, preencha o bit com 0
se o resultado for 4 ou 5, preencha o bit com 1
se o resultado for 3, então ignore e faça novamente (rejeição)

Dessa forma, podemos preencher 3 bits aleatoriamente com 0/1 e, assim, obter um número de 1 a 7.

EDIT: Esta parece ser a resposta mais simples e eficiente, então aqui está um código:

public static int random_7() {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + random_5_output_2();
        }
    }
    return returnValue;
}

private static int random_5_output_2() {
    while (true) {
        int flip = random_5();

        if (flip < 3) {
            return 0;
        }
        else if (flip > 3) {
            return 1;
        }
    }
}
Lance Roberts
fonte
1
Sempre existe o fraco espectro do problema de interrupção, uma vez que um gerador de números aleatórios ruim pode gerar muitos trios em algum momento.
Alex norte-Keys
"se o resultado for 1 ou 2, preencha o bit com 0 se o resultado for 4 ou 5, preencha o bit com 1" Qual é a lógica pela qual 1,2,4,5 foram aceitos e 3 foi rejeitado? Você pode explicar isso?
gkns
@gkns Não há lógica, você poderia ter 1 e 2 preenchimento médio com 0 bit e 3 e 4 preenchimento médio com 1. O importante é que cada opção tenha 50% de chances de ocorrer, garantindo assim que a aleatoriedade de sua função seja pelo menos tão aleatória quanto a função rand original (5). É uma ótima solução!
quer
Isso não é simples nem eficiente. O número de chamadas para random_5 por random_7 é no máximo 3, geralmente mais. Outras soluções nesta página estão mais próximas da melhor, que é em torno de 2,2.
Eyal
1
Deixa pra lá, eu perdi a parte "while returnValue == 0" #
NicholasFolk
19
int randbit( void )
{
    while( 1 )
    {
        int r = rand5();
        if( r <= 4 ) return(r & 1);
    }
}

int randint( int nbits )
{
    int result = 0;
    while( nbits-- )
    {
        result = (result<<1) | randbit();
    }
    return( result );
}

int rand7( void )
{
    while( 1 )
    {
        int r = randint( 3 ) + 1;
        if( r <= 7 ) return( r );
    }
}
Mike F
fonte
2
Uma solução correta, fazendo uma média de 30/7 = 4,29 chamadas para rand5 () por chamada para rand7 ().
Adam Rosenfield
17
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Edit: Isso não funciona muito bem. É desligado em cerca de 2 partes em 1000 (assumindo um rand5 perfeito). Os baldes recebem:

value   Count  Error%
1       11158  -0.0035
2       11144  -0.0214
3       11144  -0.0214
4       11158  -0.0035
5       11172  +0.0144
6       11177  +0.0208
7       11172  +0.0144

Ao mudar para uma soma de

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

parece ganhar uma ordem de magnitude para cada 2 adicionados

BTW: a tabela de erros acima não foi gerada por amostragem, mas pela seguinte relação de recorrência:

p[x,n]é as maneiras número output=xpode acontecer dado nchamadas para rand5.

  p[1,1] ... p[5,1] = 1
  p[6,1] ... p[7,1] = 0

  p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
  p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
  p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
  p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
  p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
  p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
  p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
BCS
fonte
8
Esta não é uma distribuição uniforme. É muito próximo do uniforme, mas não perfeitamente uniforme.
23611 Adam Rosenfield
Ah! Dados e 7's. Se você vai dizer que estou errado, não deve deixar a prova como exercício para o leitor.
BCS
45
A prova de que não é uniforme é simples: existem 5 ^ 7 maneiras possíveis de a aleatoriedade e, como 5 ^ 7 não é um múltiplo de 7, não é possível que todas as sete somas sejam igualmente prováveis. (Basicamente, resume-se a 7 sendo relativamente primo a 5 ou equivalentemente 1/7 não sendo um decimal final na base 5.) Na verdade, nem mesmo é o "mais uniforme" possível sob essa restrição: o cálculo direto mostra que o valor 5 ^ 7 = 78125 somas, o número de vezes que você obtém os valores de 1 a 7 é {1: 11145, 2: 11120, 3: 11120, 4: 11145, 5: 11190, 6: 11215, 7: 11190}.
ShreevatsaR
@ShreevatsaR Então, e se, em vez de pegar a soma de rand5 () sete vezes, fizermos 5 * 7 tomadas - isso não funcionaria? 35 ^ 7% 7 = 35 ^ 5% 7 = 0.
kba 01/01
4
@KristianAntonsen: Quantas vezes você faz rand5 (), você não consegue uma distribuição uniforme. Se você fizer isso N vezes, existem 5 ^ N saídas possíveis, que não são divisíveis por 7. (Se você fizer 35 vezes, haverá 5 ^ 35, não 35 ^ 7). Você se aproximará cada vez mais uniforme o número maior de chamadas que você usa (e pode ser qualquer número, não precisa ser divisível por 7), mas IMHO, em vez de usar um número muito grande de chamadas para rand (), você também pode usar o probabilístico algoritmo nas respostas principais, que fornece uma distribuição uniforme exata e cujo número esperado de chamadas para rand () é pequeno.
ShreevatsaR
15
int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}
Nescio
fonte
2
Uma solução correta, fazendo uma média de 30/7 = 4,29 chamadas para rand5 () por chamada para rand7 ().
Adam Rosenfield
3
Precisa ser desvio à esquerda para o algoritmo de trabalho:ans += (r < 3) << i
Woolfie
13

A seguir, produz uma distribuição uniforme em {1, 2, 3, 4, 5, 6, 7} usando um gerador de números aleatórios produzindo uma distribuição uniforme em {1, 2, 3, 4, 5}. O código é confuso, mas a lógica é clara.

public static int random_7(Random rg) {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + SimulateFairCoin(rg);
        }
    }
    return returnValue;
}

private static int SimulateFairCoin(Random rg) {
    while (true) {
        int flipOne = random_5_mod_2(rg);
        int flipTwo = random_5_mod_2(rg);

        if (flipOne == 0 && flipTwo == 1) {
            return 0;
        }
        else if (flipOne == 1 && flipTwo == 0) {
            return 1;
        }
    }
}

private static int random_5_mod_2(Random rg) {
    return random_5(rg) % 2;
}

private static int random_5(Random rg) {
    return rg.Next(5) + 1;
}    
Jason
fonte
2
Uma solução correta (que coloca você muito à frente da curva), embora não seja muito eficiente. Isso faz uma média de 25/6 = 4,17 chamadas para random_5_mod_2 por troca de moeda justa, para uma média total de 100/7 = 14,3 chamadas para random_5 () por chamada para random_7 ().
Adam Rosenfield
A vantagem desta solução em relação às demais é que ela pode ser facilmente expandida para produzir qualquer outra faixa uniformemente distribuída. Apenas selecione aleatoriamente cada um dos bits, relocando valores inválidos (como o valor 0 em nossa solução atual que produz 8 números).
DenTheMan
1
possíveis ciclos infinitos, etc.
robermorales
1
@robermorales: extremamente improvável.
Jason
13
int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

Diferentemente da solução escolhida, o algoritmo será executado em tempo constante. No entanto, faz mais 2 chamadas para rand5 do que o tempo médio de execução da solução escolhida.

Observe que este gerador não é perfeito (o número 0 tem 0,0064% mais chances do que qualquer outro número), mas, para fins mais práticos, a garantia de tempo constante provavelmente supera essa imprecisão.

Explicação

Essa solução é derivada do fato de que o número 15.624 é divisível por 7 e, portanto, se podemos gerar aleatoriamente e uniformemente números de 0 a 15.624 e, em seguida, usar o mod 7, podemos obter um gerador rand7 quase uniforme. Os números de 0 a 15.624 podem ser gerados uniformemente rolando rand5 6 vezes e usando-os para formar os dígitos de um número base 5 da seguinte maneira:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

As propriedades do mod 7, no entanto, permitem simplificar um pouco a equação:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

assim

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

torna-se

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Teoria

O número 15.624 não foi escolhido aleatoriamente, mas pode ser descoberto usando o pequeno teorema de Fermat, que afirma que se p é um número primo, então

a^(p-1) = 1 mod p

Então isso nos dá,

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 é igual a

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

Este é um número na forma de base 5 e, portanto, podemos ver que esse método pode ser usado para ir de qualquer gerador de números aleatórios para qualquer outro gerador de números aleatórios. Embora um pequeno desvio para 0 seja sempre introduzido ao usar o expoente p-1.

Para generalizar essa abordagem e para ser mais preciso, podemos ter uma função como esta:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)
Thirlan
fonte
1
Este gerador é preciso, mas não perfeitamente uniforme. Para ver isso, considere o fato de que um gerador uniforme em [0,15624] possui 15625 resultados possíveis, que não são divisíveis por 7. Isso introduz um viés para o número 0 (que tem chance 2233/15625, e os outros apenas 2232/15625). Afinal, embora o pequeno teorema de Fermat possa parecer correto à primeira vista, ele diz que (5 ^ 6)% 7 = 1, e não (5 ^ 6)% 7 = 0. O último é obviamente impossível para qualquer expoente porque 5 e 7 são ambos números primos. Acho que ainda é uma solução aceitável e editei sua postagem para refletir isso.
Aviation
12

Os problemas de lição de casa são permitidos aqui?

Essa função faz cálculos brutos da "base 5" para gerar um número entre 0 e 6.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}
Will Hartung
fonte
3
Uma solução correta (que coloca você muito à frente da curva), embora não seja muito eficiente. Isso faz uma média de 5 chamadas para rnd5 () para cada chamada para rnd7 ().
Adam Rosenfield #
Precisamos de mais alguns pls explicação
Barry
1
@ Barry - Primeiro, você não pode simplesmente adicionar dois números aleatórios, não terá uma solução linear (considere um par de dados). Agora considere "Base 5": 00, 01, 02, 03, 04, 10, 11. Que 0-6 na base 5. Portanto, precisamos gerar 2 dígitos do número base 5 e adicioná-los até que obtenha um que esteja dentro do alcance. É isso que o r2 * 5 + r1 faz. O r2> 1 laço está lá porque nunca iria querer uma alta dígito> 1.
Will Hartung
Esta solução não gera uma distribuição uniforme. Os números 1 e 7 só podem ser gerados de uma maneira, mas 2 a 6 podem ser gerados de duas maneiras: com r1 igual ao número menos 1 e r2 igual a 0 ou com r1 igual ao número menos 2 e r2 igual a 1. Assim, de 2 a 6 será devolvido em média duas vezes mais que uma ou 7.
Ted Hopp
12

Se considerarmos a restrição adicional de tentar dar a resposta mais eficiente, ou seja, uma que forneceu um fluxo de entrada I, de números inteiros uniformemente distribuídos mde 1 a 5 produz um fluxo O, de números inteiros distribuídos uniformemente de 1 a 7 do comprimento mais longo para m, digamos L(m).

A maneira mais simples de analisar isso é tratar os fluxos I e Ocomo números de 5 e 7 anos, respectivamente. Isso é alcançado pela idéia da resposta principal de pegar o fluxo a1, a2, a3,... -> a1+5*a2+5^2*a3+..e da mesma forma para o fluxo O.

Então, se fizermos uma seção do fluxo de entrada de comprimento m choose n s.t. 5^m-7^n=conde c>0e for o menor possível. Depois, há um mapa uniforme do fluxo de entrada de comprimento m para números inteiros de 1para 5^me outro mapa uniforme de números inteiros de 1 7^npara o fluxo de saída de comprimento n onde podemos ter que perder alguns casos do fluxo de entrada quando o número inteiro mapeado excede 7^n.

Portanto, isso fornece um valor para L(m)de em torno do m (log5/log7)qual é aproximadamente .82m.

A dificuldade com a análise acima é a equação 5^m-7^n=cque não é fácil de resolver exatamente e o caso em que o valor uniforme de 1para 5^mexcede 7^ne perdemos eficiência.

A questão é quão próximo do melhor valor possível de m (log5 / log7) pode ser alcançado. Por exemplo, quando esse número se aproxima de um número inteiro, podemos encontrar uma maneira de atingir esse número inteiro exato de valores de saída?

Se 5^m-7^n=c, a partir do fluxo de entrada, geramos efetivamente um número aleatório uniforme de 0para (5^m)-1e não usamos valores maiores que 7^n. No entanto, esses valores podem ser resgatados e usados ​​novamente. Eles efetivamente geram uma seqüência uniforme de números de 1 a5^m-7^n . Assim, podemos tentar usá-los e convertê-los em números de 7 anos, para que possamos criar mais valores de saída.

Se deixarmos T7(X)ser o comprimento médio da sequência de saída de random(1-7)números inteiros derivada de uma entrada uniforme de tamanho X, e assumindo isso 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.

Então, T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)como temos um comprimento sem sequência com probabilidade 7 ^ n0 / 5 ^ m com um resíduo de comprimento 5^m-7^n0com probabilidade (5^m-7^n0)/5^m).

Se continuarmos substituindo, obteremos:

T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m  = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m

Conseqüentemente

L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)

Outra maneira de colocar isso é:

If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)

O melhor caso possível é o meu original acima 5^m=7^n+s, onde, ondes<7 .

Então T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)como antes.

O pior caso é quando só podemos encontrar k e st 5 ^ m = kx7 + s.

Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)

Outros casos estão em algum lugar entre eles. Seria interessante ver o quão bem podemos fazer por m muito grande, ou seja, quão bom podemos obter o termo de erro:

T7(5^m) = m (Log5/Log7)+e(m)

Parece impossível alcançar e(m) = o(1)em geral, mas espero que possamos provar e(m)=o(m).

A coisa toda então se baseia na distribuição dos dígitos de 7 árias de 5^mpara vários valores de m.

Tenho certeza de que há muita teoria por aí que cobre isso. Posso dar uma olhada e relatar em algum momento.

Ivan
fonte
+2 (se eu pudesse) - essa era a única boa resposta (em oposição a meramente adequada). Você tem a segunda melhor resposta que cabe em números inteiros de 32 bits.
Rex Kerr
10

Aqui está uma implementação em Python funcional da resposta de Adam .

import random

def rand5():
    return random.randint(1, 5)

def rand7():
    while True:
        r = 5 * (rand5() - 1) + rand5()
        #r is now uniformly random between 1 and 25
        if (r <= 21):
            break
    #result is now uniformly random between 1 and 7
    return r % 7 + 1

Eu gosto de lançar algoritmos que estou olhando para o Python, para que eu possa brincar com eles, pensei em publicá-lo aqui na esperança de que seja útil para alguém por aí, não que demorou muito tempo para se juntar.

James McMahon
fonte
Não, isso é bastante diferente da minha resposta. Você está repetindo 21 vezes e descartando os resultados das 20 primeiras iterações. Você também está usando rand4 () e rand5 () como entrada, o que obviamente quebra as regras de usar apenas rand5 (). Finalmente, você produz uma distribuição não uniforme.
Adam Rosenfield 05/05
Me desculpe por isso. Eu estava muito cansado quando examinei essa questão, cansado o suficiente para interpretar completamente seu algoritmo. Na verdade, eu joguei no Python porque não conseguia entender por que você estava repetindo 21 vezes. Faz muito mais sentido agora. Eu fiz a coisa random.randint (1, 4) como uma abreviação, mas acho que você está correto, é contra o espírito da pergunta. Eu corrigi o código.
619 James McMahon
@robermorales - Como Adam Rosenfeld explicou em sua resposta , toda solução que fornece uma verdadeira distribuição uniforme em [1, 7] envolve algum tipo de loop de aceitação / rejeição que é potencialmente infinito. (No entanto, se rand5()é um PRNG decente, então o loop não será infinita porque, eventualmente, 5*(rand5() - 1) + rand5()vai certamente ser <= 21)
Ted Hopp
10

Por que não fazer isso simples?

int random7() {
  return random5() + (random5() % 3);
}

As chances de obter 1 e 7 nesta solução são menores devido ao módulo, no entanto, se você quer apenas uma solução rápida e legível, este é o caminho a seguir.

Ante
fonte
13
Isso não produz uma distribuição uniforme. Isso produz os números 0-6 com probabilidades 2/25, 4/25, 5/25, 5/25, 5/25, 3/25, 1/25, como pode ser verificado contando todos os 25 resultados possíveis.
23411 Adam Rosenfield
8

Supondo que rand (n) aqui significa "número inteiro aleatório em uma distribuição uniforme de 0 a n-1 ", aqui está um exemplo de código usando o randint do Python, que tem esse efeito. Ele usa apenas randint (5) e constantes para produzir o efeito de randint (7) . Um pouco bobo, na verdade

from random import randint
sum = 7
while sum >= 7:
    first = randint(0,5)   
    toadd = 9999
    while toadd>1:
        toadd = randint(0,5)
    if toadd:
        sum = first+5
    else:
        sum = first

assert 7>sum>=0 
print sum
Joshua Fox
fonte
1
@robermorales Porque o Python não possui do ... while. Poderia ter sido 1337, ou 12345, ou qualquer número> 1.
tckmn
8

A premissa por trás da resposta correta de Adam Rosenfield é:

  • x = 5 ^ n (no caso dele: n = 2)
  • manipular n chamadasand5 para obter um número y dentro do intervalo [1, x]
  • z = ((int) (x / 7)) * 7
  • se y> z, tente novamente. caso contrário, retorne y% 7 + 1

Quando n é igual a 2, você tem 4 possibilidades de descarte: y = {22, 23, 24, 25}. Se você usar n é igual a 6, você tem apenas 1 descarte: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Você chama rand5 mais vezes. No entanto, você tem uma chance muito menor de obter um valor de descarte (ou um loop infinito). Se existe uma maneira de não obter um valor possível de descarte para y, ainda não o encontrei.

Dinah
fonte
1
Provavelmente, não há caso sem valores descartáveis ​​- se não houvesse descarte, 5 ^ n e 7 ^ m teriam um fator em comum. Mas eles são (poderes de) primos, então não o fazem.
Rex Kerr
8

Aqui está a minha resposta:

static struct rand_buffer {
  unsigned v, count;
} buf2, buf3;

void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
  buf->v = buf->v * n + v;
  ++buf->count;
}

#define PUSH(n, v)  push (&buf##n, n, v)

int rand16 (void)
{
  int v = buf2.v & 0xf;
  buf2.v >>= 4;
  buf2.count -= 4;
  return v;
}

int rand9 (void)
{
  int v = buf3.v % 9;
  buf3.v /= 9;
  buf3.count -= 2;
  return v;
}

int rand7 (void)
{
  if (buf3.count >= 2) {
    int v = rand9 ();

    if (v < 7)
      return v % 7 + 1;

    PUSH (2, v - 7);
  }

  for (;;) {
    if (buf2.count >= 4) {
      int v = rand16 ();

      if (v < 14) {
        PUSH (2, v / 7);
        return v % 7 + 1;
      }

      PUSH (2, v - 14);
    }

    // Get a number between 0 & 25
    int v = 5 * (rand5 () - 1) + rand5 () - 1;

    if (v < 21) {
      PUSH (3, v / 7);
      return v % 7 + 1;
    }

    v -= 21;
    PUSH (2, v & 1);
    PUSH (2, v >> 1);
  }
}

É um pouco mais complicado do que outros, mas acredito que minimiza as chamadas para o rand5. Como em outras soluções, há uma pequena probabilidade de que ele possa se repetir por um longo tempo.

Chris Suter
fonte
Isso produz uma distribuição não muito diferente das outras soluções, mas tem a desvantagem de ser desnecessariamente complexo. Ele também sofre com a possibilidade não determinística de loop para sempre comprovadamente incorreta se os números forem realmente aleatórios. Eu ainda acho que as que produzem uma distribuição um pouco menos uniforme (embora ainda muito mais que adequada), mas garantem que o comportamento determinista é melhor.
21420
@Pax: Por favor, explique-me como isso produz uma distribuição não uniforme. Minha análise do código, bem como meus próprios testes, indicam que isso produz uma distribuição uniforme. Como discutimos anteriormente, é impossível produzir uma distribuição perfeitamente uniforme e ter um limite superior garantido em tempo constante do tempo de execução.
9339 Adam Rosenfield
6

Enquanto não houver sete possibilidades para escolher, desenhe outro número aleatório, que multiplique o número de possibilidades por cinco. Em Perl:

$num = 0;
$possibilities = 1;

sub rand7
{
  while( $possibilities < 7 )
  {
    $num = $num * 5 + int(rand(5));
    $possibilities *= 5;
  }
  my $result = $num % 7;
  $num = int( $num / 7 );
  $possibilities /= 7;
  return $result;
}
user223264
fonte
sua distribuição não é uniforme, pelo menos na primeira chamada. Na verdade, $possibilitiessempre tem que crescer para 25 para sair do loop e retornar. Portanto, seu primeiro resultado é [0-124] % 7, que não é distribuído uniformemente porque 125 % 7 != 0(na verdade, é 6).
22133 bernard paulus
6

Não gosto de intervalos a partir de 1, então vou começar de 0 :-)

unsigned rand5()
{
    return rand() % 5;
}

unsigned rand7()
{
    int r;

    do
    {
        r =         rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
        r = r * 5 + rand5();
    } while (r > 15623);

    return r / 2232;
}
fredoverflow
fonte
Este é um vencedor. Isso produz todos os 7 resultados com igual probabilidade. from collections import defaultdict def r7(n): if not n: yield [] else: for i in range(1, 6): for j in r7(n-1): yield [i] + j def test_r7(): d = defaultdict(int) for x in r7(6): s = (((((((((x[5] * 5) + x[4]) * 5) + x[3]) * 5) + x[2]) * 5) + x[1]) * 5) + x[0] if s <= 15623: d[s % 7] += 1 print d
precisa saber é o seguinte
5

Lá vai você, distribuição uniforme e zero rand5 chamadas.

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

Precisa colocar sementes com antecedência.

Kugel
fonte
5

Sei que foi respondido, mas parece que está funcionando bem, mas não posso dizer se existe algum viés. Meu 'teste' sugere que é, pelo menos, razoável.

Talvez Adam Rosenfield tenha a gentileza de comentar?

Minha idéia (ingênua?) É esta:

Acumule rand5's até que haja bits aleatórios suficientes para criar um rand7. Isso leva no máximo 2 rand5's. Para obter o número rand7, uso o valor acumulado mod 7.

Para evitar o transbordamento do acumulador, e como o acumulador é o mod 7, eu uso o mod 7 do acumulador:

(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7

A função rand7 () segue:

(Eu deixei o intervalo de rand5 ser 0-4 e rand7 também é 0-6.)

int rand7(){
  static int    a=0;
  static int    e=0;
  int       r;
  a = a * 5 + rand5();
  e = e + 5;        // added 5/7ths of a rand7 number
  if ( e<7 ){
    a = a * 5 + rand5();
    e = e + 5;  // another 5/7ths
  }
  r = a % 7;
  e = e - 7;        // removed a rand7 number
  a = a % 7;
  return r;
}

Edit: Adicionado resultados para 100 milhões de tentativas.

Funções de rand 'reais' mod 5 ou 7

rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046

Meu rand7

A média parece boa e as distribuições de números também parecem boas.

randt: avg = 3.000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943

philcolbourn
fonte
Você provavelmente deve olhar para a correlação seqüencial. Eu acho que se você pegar pares sucessivos (cada número "aleatório" emparelhado com o seu antecessor), poderá encontrar coisas surpreendentes. Você não explicou por que deve manter a distribuição uniforme, pelo menos. Um programa de trabalho normalmente deve começar com uma explicação de por que ele funciona.
Ian
A correlação seqüencial se aplicaria a muitas dessas soluções?
philcolbourn
A correlação seqüencial se aplicaria a muitas dessas soluções? Já faz um tempo desde que eu tentei isso e pensei que tinha explicado. Olhando para isso agora, parece que estou acumulando bits aleatórios em um pool do rand5, garantindo que o suficiente tenha sido acumulado antes de retirar o suficiente para criar um número rand7 e garantindo que eu não transborde meu acumulador.
philcolbourn
4

Existem algoritmos elegantes citados acima, mas aqui está uma maneira de abordá-lo, embora possa ser indireto. Estou assumindo valores gerados a partir de 0.

R2 = gerador de números aleatórios que fornece valores menores que 2 (espaço da amostra = {0, 1})
R8 = gerador de números aleatórios que fornece valores menores que 8 (espaço da amostra = {0, 1, 2, 3, 4, 5, 6, 7 })

Para gerar R8 a partir do R2, você executará o R2 três vezes e usará o resultado combinado de todas as 3 execuções como um número binário com 3 dígitos. Aqui está o intervalo de valores quando o R2 é executado três vezes:

0 0 0 -> 0
.
.
1 1 1 -> 7

Agora, para gerar R7 a partir de R8, simplesmente rodamos R7 novamente se retornar 7:

int R7() {
  do {
    x = R8();
  } while (x > 6)
  return x;
}

A solução indireta é gerar R2 a partir de R5 (assim como geramos R7 a partir de R8), depois R8 a partir de R2 e R7 a partir de R8.

Ashwin
fonte
como várias outras, essa abordagem pode levar um tempo arbitrariamente longo por chamada R7, já que você pode obter uma longa sequência de setes de R8.
Alex norte-Keys
4

Aqui está uma solução que se encaixa inteiramente em números inteiros e está dentro de cerca de 4% do ideal (ou seja, usa 1,26 números aleatórios em {0..4} para cada um em {0..6}). O código está em Scala, mas a matemática deve ser razoavelmente clara em qualquer idioma: você tira vantagem do fato de 7 ^ 9 + 7 ^ 8 estar muito próximo de 5 ^ 11. Então, você escolhe um número de 11 dígitos na base 5 e, em seguida, interpreta-o como um número de 9 dígitos na base 7, se estiver no intervalo (fornecendo 9 números base 7) ou como um número de 8 dígitos, se estiver acima do número de 9 dígitos, etc. .:

abstract class RNG {
  def apply(): Int
}

class Random5 extends RNG {
  val rng = new scala.util.Random
  var count = 0
  def apply() = { count += 1 ; rng.nextInt(5) }
}

class FiveSevener(five: RNG) {
  val sevens = new Array[Int](9)
  var nsevens = 0
  val to9 = 40353607;
  val to8 = 5764801;
  val to7 = 823543;
  def loadSevens(value: Int, count: Int) {
    nsevens = 0;
    var remaining = value;
    while (nsevens < count) {
      sevens(nsevens) = remaining % 7
      remaining /= 7
      nsevens += 1
    }
  }
  def loadSevens {
    var fivepow11 = 0;
    var i=0
    while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
    if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
    fivepow11 -= to9
    if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
    fivepow11 -= to8
    if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
    else loadSevens
  }
  def apply() = {
    if (nsevens==0) loadSevens
    nsevens -= 1
    sevens(nsevens)
  }
}

Se você colar um teste no intérprete (REPL, na verdade), obtém:

scala> val five = new Random5
five: Random5 = Random5@e9c592

scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423

scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)

scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000

scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)

scala> five.count
res1: Int = 125902876

A distribuição é agradável e plana (dentro de cerca de 10k de 1/7 de 10 ^ 8 em cada compartimento, como esperado de uma distribuição aproximadamente gaussiana).

Rex Kerr
fonte
3

Usando um total contínuo , você pode

  • manter uma distribuição igual; e
  • não precisa sacrificar nenhum elemento na sequência aleatória.

Esses dois problemas são um problema com as rand(5)+rand(5)...soluções simplistas do tipo. O código Python a seguir mostra como implementá-lo (a maioria disso está provando a distribuição).

import random
x = []
for i in range (0,7):
    x.append (0)
t = 0
tt = 0
for i in range (0,700000):
    ########################################
    #####            qq.py             #####
    r = int (random.random () * 5)
    t = (t + r) % 7
    ########################################
    #####       qq_notsogood.py        #####
    #r = 20
    #while r > 6:
        #r =     int (random.random () * 5)
        #r = r + int (random.random () * 5)
    #t = r
    ########################################
    x[t] = x[t] + 1
    tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
    if x[i] < low:
        low = x[i]
    if x[i] > high:
        high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)

E esta saída mostra os resultados:

pax$ python qq.py
0:   99908 14.27257
1:  100029 14.28986
2:  100327 14.33243
3:  100395 14.34214
4:   99104 14.15771
5:   99829 14.26129
6:  100408 14.34400
Variation = 1304 (0.18629%)

pax$ python qq.py
0:   99547 14.22100
1:  100229 14.31843
2:  100078 14.29686
3:   99451 14.20729
4:  100284 14.32629
5:  100038 14.29114
6:  100373 14.33900
Variation = 922 (0.13171%)

pax$ python qq.py
0:  100481 14.35443
1:   99188 14.16971
2:  100284 14.32629
3:  100222 14.31743
4:   99960 14.28000
5:   99426 14.20371
6:  100439 14.34843
Variation = 1293 (0.18471%)

Um simplista rand(5)+rand(5), ignorando os casos em que isso retorna mais de 6, tem uma variação típica de 18%, 100 vezes a do método mostrado acima:

pax$ python qq_notsogood.py
0:   31756 4.53657
1:   63304 9.04343
2:   95507 13.64386
3:  127825 18.26071
4:  158851 22.69300
5:  127567 18.22386
6:   95190 13.59857
Variation = 127095 (18.15643%)

pax$ python qq_notsogood.py
0:   31792 4.54171
1:   63637 9.09100
2:   95641 13.66300
3:  127627 18.23243
4:  158751 22.67871
5:  126782 18.11171
6:   95770 13.68143
Variation = 126959 (18.13700%)

pax$ python qq_notsogood.py
0:   31955 4.56500
1:   63485 9.06929
2:   94849 13.54986
3:  127737 18.24814
4:  159687 22.81243
5:  127391 18.19871
6:   94896 13.55657
Variation = 127732 (18.24743%)

E, seguindo o conselho da Nixuz, limpei o script para que você possa extrair e usar as rand7...coisas:

import random

# rand5() returns 0 through 4 inclusive.

def rand5():
    return int (random.random () * 5)

# rand7() generator returns 0 through 6 inclusive (using rand5()).

def rand7():
    rand7ret = 0
    while True:
        rand7ret = (rand7ret + rand5()) % 7
        yield rand7ret

# Number of test runs.

count = 700000

# Work out distribution.

distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
    r = rgen.next()
    distrib[r] = distrib[r] + 1

# Print distributions and calculate variation.

high = distrib[0]
low = distrib[0]
for i in range (0,7):
    print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
    if distrib[i] < low:
        low = distrib[i]
    if distrib[i] > high:
        high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
paxdiablo
fonte
2
Err, deixe-me reformular isso. Dado que um x específico foi produzido em algum momento da sequência, apenas 5 dos 7 números podem ser produzidos para o próximo número na sequência. Um verdadeiro RNG teria todas as amostras independentes umas das outras, mas nesse caso elas claramente não são.
Adam Rosenfield #
3
É verdade que a pergunta original não especifica se as funções de entrada e saída produzem amostras independentes e de distribuição idêntica (iid), mas acho que é uma expectativa razoável que, se a entrada rand5 () for iid, a saída rand7 () também deve ser iid. Se você acha que isso não é razoável, divirta-se usando seu RNG não-iid.
Adam Rosenfield #
1
Então, qual é a palavra dos matemáticos da universidade?
Adam Rosenfield
1
Esta solução está claramente quebrada. É óbvio que você precisa ligar para o rand5 (em média) mais de uma vez por chamada para o rand7, e esta solução não. Portanto, os resultados não podem ser aleatórios por qualquer definição sensata de aleatório.
9139 Chris Suter
1
@Pax A cada iteração da sua função, ele pode retornar apenas um dos cinco valores diferentes (embora no intervalo de 0 a 6). A primeira iteração pode retornar apenas um número no intervalo de 0 a 4. Portanto, deve ficar claro que, embora sua função possa ter distribuição uniforme, as amostras não são independentes, ou seja, estão correlacionadas, o que não é algo que você deseja em um gerador de números aleatórios.
9139 Chris Suter
3

Essa resposta é mais um experimento para obter o máximo de entropia possível da função Rand5. Portanto, não é claro e quase certamente muito mais lento que outras implementações.

Assumindo a distribuição uniforme de 0-4 e a distribuição uniforme resultante de 0-6:

public class SevenFromFive
{
  public SevenFromFive()
  {
    // this outputs a uniform ditribution but for some reason including it 
    // screws up the output distribution
    // open question Why?
    this.fifth = new ProbabilityCondensor(5, b => {});
    this.eigth = new ProbabilityCondensor(8, AddEntropy);
  } 

  private static Random r = new Random();
  private static uint Rand5()
  {
    return (uint)r.Next(0,5);
  }

  private class ProbabilityCondensor
  {
    private readonly int samples;
    private int counter;
    private int store;
    private readonly Action<bool> output;

    public ProbabilityCondensor(int chanceOfTrueReciprocal,
      Action<bool> output)
    {
      this.output = output;
      this.samples = chanceOfTrueReciprocal - 1;  
    }

    public void Add(bool bit)
    {
      this.counter++;
      if (bit)
        this.store++;   
      if (counter == samples)
      {
        bool? e;
        if (store == 0)
          e = false;
        else if (store == 1)
          e = true;
        else
          e = null;// discard for now       
        counter = 0;
        store = 0;
        if (e.HasValue)
          output(e.Value);
      }
    }
  }

  ulong buffer = 0;
  const ulong Mask = 7UL;
  int bitsAvail = 0;
  private readonly ProbabilityCondensor fifth;
  private readonly ProbabilityCondensor eigth;

  private void AddEntropy(bool bit)
  {
    buffer <<= 1;
    if (bit)
      buffer |= 1;      
    bitsAvail++;
  }

  private void AddTwoBitsEntropy(uint u)
  {
    buffer <<= 2;
    buffer |= (u & 3UL);    
    bitsAvail += 2;
  }

  public uint Rand7()
  {
    uint selection;   
    do
    {
      while (bitsAvail < 3)
      {
        var x = Rand5();
        if (x < 4)
        {
          // put the two low order bits straight in
          AddTwoBitsEntropy(x);
          fifth.Add(false);
        }
        else
        { 
          fifth.Add(true);
        }
      }
      // read 3 bits
      selection = (uint)((buffer & Mask));
      bitsAvail -= 3;     
      buffer >>= 3;
      if (selection == 7)
        eigth.Add(true);
      else
        eigth.Add(false);
    }
    while (selection == 7);   
    return selection;
  }
}

O número de bits adicionados ao buffer por chamada para Rand5 é atualmente de 4/5 * 2, portanto 1.6. Se o valor da probabilidade 1/5 estiver incluído, aumenta em 0,05 para 1,65, mas veja o comentário no código em que tive que desativar isso.

Bits consumidos pela chamada para Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
Isso é 3 + 3/8 + 3/64 + 3/512 ... então aproximadamente 3,42

Ao extrair informações dos setes, recupero 1/8 * 1/7 bits por chamada, aproximadamente 0,018

Isso fornece um consumo líquido de 3,4 bits por chamada, o que significa que a taxa é de 2,125 chamadas para Rand5 para cada Rand7. O ideal deve ser 2.1.

Eu imagino que essa abordagem seja significativamente mais lenta do que muitas outras aqui, a menos que o custo da ligação para o Rand5 seja extremamente caro (digamos, chamar alguma fonte externa de entropia).

ShuggyCoUk
fonte
Sua solução parece correta, além de alguns erros simples: "if (count> 1)" deveria ser "if (count <= 1)", e o "i ++" que ocorre logo em seguida deve estar dentro dos chavetas que a precedem. Não tenho certeza se BitsSet () está correto ou não, mas isso é um tanto irrelevante.
Adam Rosenfield
No geral, porém, sua função é muito difícil de entender. Faz um uso ligeiramente melhor da entropia do que poderia, às custas de mais complicações. Também não há razão para preencher inicialmente o buffer com 35 bits aleatórios na primeira chamada, quando três forem suficientes.
Adam Rosenfield
Corrigi o <= obrigado, o i ++ realmente deveria estar lá. Isso deve acontecer nos casos zero e 1 (adicionando 1 ou zero respectivamente ao buffer). Isso absolutamente não é o que eu sugeriria usar, é terrivelmente complicado. Eu só estava interessado em saber o quão perto eu poderia chegar dos limites teóricos de entropia inerentes ao problema ... Obrigado pelo feedback. Ironicamente o enchimento do tampão na primeira chamada foi para torná-lo mais simples de escrever :)
ShuggyCoUk
Reescrevi isso para ser mais fácil de entender (ao custo da velocidade), mas também o corrigi. Ainda não é o ideal, por algum motivo os 1/5 bits causam problemas, mesmo que sejam de contagem uniforme.
ShuggyCoUk
3

em php

function rand1to7() {
    do {
        $output_value = 0;
        for ($i = 0; $i < 28; $i++) {
            $output_value += rand1to5();
        }
    while ($output_value != 140);
    $output_value -= 12;
    return floor($output_value / 16);
}

loops para produzir um número aleatório entre 16 e 127, divide por dezesseis para criar um ponto flutuante entre 1 e 7,9375 e, em seguida, arredonda para baixo para obter um int entre 1 e 7. Se não me engano, há uma chance de 16/112 de obter qualquer um dos 7 resultados.

dqhendricks
fonte
embora exista provavelmente uma resposta mais fácil semelhante a essa, sem loop condicional e módulo em vez de floor. Eu simplesmente não posso triturar os números agora.
Dqhendricks
3
extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
maxchengcn
fonte
problema: isso retorna de maneira não uniforme no intervalo de 0 a 7, e não de 0 a 6. Na verdade, você pode ter 7 = 111bcomp(7) = 8 / 125
bernard paulus
3

Acho que tenho quatro respostas, duas dando soluções exatas como a de @Adam Rosenfield, mas sem o problema do loop infinito, e outras duas com solução quase perfeita, mas com implementação mais rápida que a primeira.

A melhor solução exata requer 7 chamadas rand5, mas vamos prosseguir para entender.

Método 1 - Exato

A força da resposta de Adam é que ela fornece uma distribuição uniforme perfeita e há uma probabilidade muito alta (21/25) de que apenas duas chamadas para rand5 () serão necessárias. No entanto, o pior caso é o loop infinito.

A primeira solução abaixo também fornece uma distribuição uniforme perfeita, mas requer um total de 42 chamadas para rand5. Sem loops infinitos.

Aqui está uma implementação do R:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1

Para pessoas que não estão familiarizadas com o R, aqui está uma versão simplificada:

rand7 = function(){
  r = 0 
  for(i in 0:6){
    r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
  }
  return r %% 7 + 1
}

A distribuição de rand5será preservada. Se fizermos as contas, cada uma das 7 iterações do loop possui 5 ^ 6 combinações possíveis, portanto, o número total de combinações possíveis é (7 * 5^6) %% 7 = 0. Assim, podemos dividir os números aleatórios gerados em grupos iguais de 7. Veja o método dois para mais discussão sobre isso.

Aqui estão todas as combinações possíveis:

table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
15625 15625 15625 15625 15625 15625 15625 

Eu acho que é fácil mostrar que o método de Adam será muito mais rápido. A probabilidade de haver 42 chamadas ou mais rand5na solução de Adam é muito pequena ( (4/25)^21 ~ 10^(-17)).

Método 2 - Não exato

Agora, o segundo método, que é quase uniforme, mas requer 6 chamadas para rand5:

rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Aqui está uma versão simplificada:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return r %% 7 + 1
}

Esta é essencialmente uma iteração do método 1. Se gerarmos todas as combinações possíveis, aqui estão as contagens resultantes:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

   1    2    3    4    5    6    7 
2233 2232 2232 2232 2232 2232 2232

Um número aparecerá mais uma vez nos 5^6 = 15625testes.

Agora, no método 1, adicionando 1 a 6, movemos o número 2233 para cada um dos pontos sucessivos. Assim, o número total de combinações corresponderá. Isso funciona porque 5 ^ 6 %% 7 = 1 e, depois, fazemos 7 variações apropriadas (7 * 5 ^ 6 %% 7 = 0).

Método 3 - Exato

Se o argumento dos métodos 1 e 2 for entendido, o método 3 segue e requer apenas 7 chamadas para rand5. Nesse ponto, acho que esse é o número mínimo de chamadas necessárias para uma solução exata.

Aqui está uma implementação do R:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1

Para pessoas que não estão familiarizadas com o R, aqui está uma versão simplificada:

rand7 = function(){
  r = 0 
  for(i in 1:7){
    r = r + i * rand5()
  }
  return r %% 7 + 1
}

A distribuição de rand5será preservada. Se fizermos as contas, cada uma das 7 iterações do loop tem 5 resultados possíveis, portanto, o número total de combinações possíveis (7 * 5) %% 7 = 0. Assim, podemos dividir os números aleatórios gerados em grupos iguais de 7. Veja o método um e dois para mais discussão sobre isso.

Aqui estão todas as combinações possíveis:

table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)

1 2 3 4 5 6 7  
5 5 5 5 5 5 5 

Eu acho que é fácil mostrar que o método de Adam ainda funcionará mais rápido. A probabilidade de que haja 7 ou mais chamadas rand5na solução de Adam ainda é pequena ( (4/25)^3 ~ 0.004).

Método 4 - Não exato

Essa é uma variação menor do segundo método. É quase uniforme, mas requer 7 chamadas para rand5, isto é mais um para o método 2:

rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Aqui está uma versão simplificada:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return (r+rand5()) %% 7 + 1
}

Se gerarmos todas as combinações possíveis, aqui estão as contagens resultantes:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
11160 11161 11161 11161 11161 11161 11160

Dois números aparecerão uma vez menos nos 5^7 = 78125testes. Para a maioria dos propósitos, eu posso viver com isso.

Shambho
fonte
1
Não estou familiarizado com R, mas, a menos que esteja entendendo mal como isso funciona, o método 1 não é exato. Tem (5 ^ 6) ^ 7 = 5 ^ 42 resultados possíveis, não (5 ^ 6) * 7; 5 ^ 42 não é divisível por 7. Da mesma forma, o método 3 não é exato. Tem 5 ^ 7 resultados possíveis, não 5 * 7. (A última iteração do loop no método 3 com i=7também não tem nenhum efeito, uma vez que a adição 7*rand5()de rnão alterar o valor do rmod 7.)
Adam Rosenfield
2

A função que você precisa é rand1_7 () , escrevi rand1_5 () para que você possa testá-lo e plotá-lo.

import numpy
def rand1_5():
    return numpy.random.randint(5)+1

def rand1_7():
    q = 0
    for i in xrange(7):  q+= rand1_5()
    return q%7 + 1
Andrea Ambu
fonte