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?

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. :)

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.

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 ₂ 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. a₁ a₂ a₃ ..., em que cada dígito a_i é 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 ² + 1/5 ³ + ... = 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.

(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()

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;
        }
    }
}

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

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]

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

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;
}    

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)

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;
}

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.

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.

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.

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

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.

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.

Simples e eficiente:

int rand7 ( void )
{
    return 4; // this number has been calculated using
              // rand5() and is in the range 1..7
}

(Inspirado em Qual é o seu desenho animado favorito de "programador"? ).

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;
}

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;
}

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.

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

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.

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).

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)

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).

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.

extern int r5();

int r7() {
    return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}

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.

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