Dada una función que produce un entero aleatorio en el rango de 1 a 5, escriba una función que produzca un entero aleatorio en el rango de 1 a 7.

1. ¿Qué es una solución simple?
2. ¿Cuál es una solución efectiva para reducir el uso de memoria o ejecutarse en una CPU más lenta?

Esto es equivalente a la solución de Adam Rosenfield, pero puede ser un poco más claro para algunos lectores. Se supone que rand5 () es una función que devuelve un entero estadísticamente aleatorio en el rango 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? Piénselo de esta manera: imagine imprimir esta matriz de doble dimensión en papel, pegarla en un tablero de dardos y arrojarle al azar dardos. Si alcanza un valor distinto de cero, es un valor estadísticamente aleatorio entre 1 y 7, ya que hay un número igual de valores distintos de cero para elegir. Si golpeas un cero, sigue tirando el dardo hasta que golpees un no cero. Eso es lo que está haciendo este código: los índices i y j seleccionan aleatoriamente una ubicación en el tablero de dardos, y si no obtenemos un buen resultado, seguimos lanzando dardos.

Como dijo Adam, esto puede durar para siempre en el peor de los casos, pero estadísticamente el peor de los casos nunca sucede. :)

No existe una solución (exactamente correcta) que se ejecute en una cantidad de tiempo constante, ya que 1/7 es un decimal infinito en la base 5. Una solución simple sería utilizar un muestreo de rechazo, por ejemplo:

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

Esto tiene un tiempo de ejecución esperado de 25/21 = 1.19 iteraciones del bucle, pero hay una probabilidad infinitamente pequeña de bucle para siempre.

Me gustaría agregar otra respuesta, además de mi primera respuesta . Esta respuesta intenta minimizar el número de llamadas a rand5()por llamada rand7(), para maximizar el uso de la aleatoriedad. Es decir, si considera que la aleatoriedad es un recurso valioso, queremos usar la mayor cantidad posible, sin tirar ningún fragmento aleatorio. Esta respuesta también tiene algunas similitudes con la lógica presentada en la respuesta de Ivan .

La entropía de una variable aleatoria es una cantidad bien definida. Para una variable aleatoria que toma N estados con probabilidades iguales (una distribución uniforme), la entropía es log ₂ N. Por lo tanto, rand5()tiene aproximadamente 2.32193 bits de entropía y rand7()tiene aproximadamente 2.80735 bits de entropía. Si esperamos maximizar nuestro uso de aleatoriedad, necesitamos usar todos los 2.32193 bits de entropía de cada llamada a rand5(), y aplicarlos para generar 2.80735 bits de entropía necesarios para cada llamada a rand7(). El límite fundamental, entonces, es que no podemos hacer nada mejor que log (7) / log (5) = 1.20906 llamadas a rand5()por llamada a rand7().

Notas al margen: todos los logaritmos en esta respuesta serán de base 2 a menos que se especifique lo contrario. rand5()se supondrá que devuelve números en el rango [0, 4], y rand7()se supondrá que devuelve números en el rango [0, 6]. Ajustar los rangos a [1, 5] y [1, 7] respectivamente es trivial.

Entonces, ¿Cómo lo hacemos? Generamos un número real aleatorio infinitamente preciso entre 0 y 1 (simule por el momento que realmente podríamos calcular y almacenar un número tan infinitamente preciso; lo arreglaremos más adelante). Podemos generar dicho número generando sus dígitos en la base 5: elegimos el número aleatorio 0. a₁ a₂ a₃ ..., donde cada dígito a _ies elegido por una llamada a rand5(). Por ejemplo, si nuestro RNG eligió a _i= 1 para todos i, ignorando el hecho de que eso no es muy aleatorio, eso correspondería al número real 1/5 + 1/5 ² + 1/5 ³ + ... = 1/4 (suma de una serie geométrica).

Bien, entonces hemos elegido un número real aleatorio entre 0 y 1. Ahora afirmo que dicho número aleatorio está distribuido uniformemente. Intuitivamente, esto es fácil de entender, ya que cada dígito se seleccionó de manera uniforme y el número es infinitamente preciso. Sin embargo, una prueba formal de esto es algo más complicada, ya que ahora estamos tratando con una distribución continua en lugar de una distribución discreta, por lo que debemos demostrar que la probabilidad de que nuestro número se encuentre en un intervalo [ a, b] es igual a la longitud de ese intervalo, b - a. La prueba se deja como un ejercicio para el lector =).

Ahora que tenemos un número real aleatorio seleccionado uniformemente del rango [0, 1], necesitamos convertirlo a una serie de números aleatorios uniformes en el rango [0, 6] para generar la salida de rand7(). Cómo hacemos esto? Justo lo contrario de lo que acabamos de hacer: lo convertimos a un decimal infinitamente preciso en base 7, y luego cada dígito de base 7 corresponderá a una salida de rand7().

Tomando el ejemplo de antes, si nuestro rand5()produce un flujo infinito de 1, entonces nuestro número real aleatorio será 1/4. Con la conversión de 1/4 a base 7, obtenemos el decimal infinito 0.15151515 ..., por lo que produciremos como salida 1, 5, 1, 5, 1, 5, etc.

Bien, tenemos la idea principal, pero nos quedan dos problemas: no podemos calcular o almacenar un número real infinitamente preciso, entonces, ¿cómo lidiamos con solo una porción finita? En segundo lugar, ¿cómo lo convertimos realmente a base 7?

Una forma de convertir un número entre 0 y 1 a base 7 es la siguiente:

1. Multiplicar por 7
2. La parte integral del resultado es la siguiente base de 7 dígitos
3. Resta la parte integral, dejando solo la parte fraccional
4. Ir al paso 1

Para lidiar con el problema de la precisión infinita, calculamos un resultado parcial y también almacenamos un límite superior sobre cuál podría ser el resultado. Es decir, supongamos que llamamos rand5()dos veces y devolvió 1 las dos veces. El número que hemos generado hasta ahora es 0.11 (base 5). Cualquiera que sea el resto de las infinitas series de llamadas que se rand5()producirán, el número real aleatorio que estamos generando nunca será mayor que 0.12: siempre es cierto que 0.11 ≤ 0.11xyz ... <0.12.

Por lo tanto, al realizar un seguimiento del número actual hasta el momento y el valor máximo que podría tomar, convertimos ambos números a la base 7. Si están de acuerdo con los primeros kdígitos, entonces podemos generar con seguridad los siguientes kdígitos, independientemente de lo que ¡flujo infinito de base 5 dígitos son, nunca afectarán los siguientes kdígitos de la representación de base 7!

Y ese es el algoritmo: para generar la siguiente salida de rand7(), generamos solo tantos dígitos rand5()como sea necesario para garantizar que sepamos con certeza el valor del siguiente dígito en la conversión del número real aleatorio a la base 7. Aquí está Una implementación de Python, con un arnés de prueba:

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)

Tenga en cuenta que rand7_gen()devuelve un generador, ya que tiene un estado interno que implica la conversión del número a la base 7. El arnés de prueba llama next(r7)10000 veces para producir 10000 números aleatorios, y luego mide su distribución. Solo se usa matemática entera, por lo que los resultados son exactamente correctos.

También tenga en cuenta que los números aquí se vuelven muy grandes, muy rápidos. Las potencias de 5 y 7 crecen rápidamente. Por lo tanto, el rendimiento comenzará a degradarse notablemente después de generar muchos números aleatorios, debido a la aritmética bignum. Pero recuerde aquí, mi objetivo era maximizar el uso de bits aleatorios, no maximizar el rendimiento (aunque ese es un objetivo secundario).

En una corrida de esto, hice 12091 llamadas a rand5()10000 llamadas a rand7(), logrando el mínimo de llamadas log (7) / log (5) en promedio a 4 cifras significativas, y el resultado resultante fue uniforme.

Para portar este código a un idioma que no tenga enteros arbitrariamente grandes incorporados, tendrá que limitar los valores pow5y pow7al valor máximo de su tipo integral nativo; si se vuelven demasiado grandes, reinicie todo y empezar de nuevo. Esto aumentará el número promedio de llamadas rand5()por llamada a rand7()muy ligeramente, pero es de esperar que no aumente demasiado incluso para enteros de 32 o 64 bits.

(He robado la respuesta de Adam Rosenfeld y la hice correr un 7% más rápido).

Suponga que rand5 () devuelve uno de {0,1,2,3,4} con igual distribución y el objetivo es devolver {0,1,2,3,4,5,6} con igual distribución.

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 realizando un seguimiento del valor más grande que el ciclo puede hacer en la variable max. Si el resultado hasta ahora es entre max% 7 y max-1, el resultado se distribuirá uniformemente en ese rango. Si no, usamos el resto, que es aleatorio entre 0 y max% 7-1, y otra llamada a rand () para hacer un nuevo número y un nuevo max. Entonces comenzamos de nuevo.

Editar: esperar número de veces para llamar a rand5 () es x en esta ecuación:

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 se puede representar en una secuencia de 3 bits

Use rand (5) para llenar aleatoriamente cada bit con 0 o 1.
Por ejemplo: llame a rand (5) y

si el resultado es 1 o 2, llene el bit con 0
si el resultado es 4 o 5, llene el bit con 1
si el resultado es 3, luego ignórelo y vuelva a hacerlo (rechazo)

De esta manera podemos llenar 3 bits al azar con 0/1 y así obtener un número del 1 al 7.

EDITAR: Esta parece ser la respuesta más simple y eficiente, así que aquí hay un código para ello:

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

Editar: Eso no funciona del todo. Está apagado por aproximadamente 2 partes en 1000 (suponiendo un rand5 perfecto). Los cubos obtienen:

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

Al cambiar a una suma de

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

parece ganar un orden de magnitud por cada 2 agregados

Por cierto: la tabla de errores anterior no se generó a través del muestreo, sino por la siguiente relación de recurrencia:

p[x,n]es la cantidad de formas en que output=xpueden suceder las nllamadas a 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
     }
}

Lo siguiente produce una distribución uniforme en {1, 2, 3, 4, 5, 6, 7} usando un generador de números aleatorios que produce una distribución uniforme en {1, 2, 3, 4, 5}. El código es desordenado, pero la lógica es 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;
}

A diferencia de la solución elegida, el algoritmo se ejecutará en tiempo constante. Sin embargo, realiza 2 llamadas más a rand5 que el tiempo de ejecución promedio de la solución elegida.

Tenga en cuenta que este generador no es perfecto (el número 0 tiene un 0.0064% más de posibilidades que cualquier otro número), pero para la mayoría de los propósitos prácticos, la garantía de tiempo constante probablemente supere esta inexactitud.

Explicación

Esta solución se deriva del hecho de que el número 15,624 es divisible por 7 y, por lo tanto, si podemos generar de manera aleatoria y uniforme números del 0 al 15,624 y luego tomar mod 7, podemos obtener un generador rand7 casi uniforme. Los números del 0 al 15,624 pueden generarse de manera uniforme haciendo rodar rand5 6 veces y usándolos para formar los dígitos de un número base 5 de la siguiente manera:

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

Sin embargo, las propiedades del mod 7 nos permiten simplificar un poco la ecuación:

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

Entonces

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

se convierte

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

Teoría

El número 15,624 no se eligió al azar, pero se puede descubrir utilizando el pequeño teorema de fermat, que establece que si p es un número primo, entonces

a^(p-1) = 1 mod p

Entonces esto nos da,

(5^6)-1 = 0 mod 7

(5 ^ 6) -1 es igual a

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

Este es un número en forma de base 5 y, por lo tanto, podemos ver que este método puede usarse para pasar de cualquier generador de números aleatorios a cualquier otro generador de números aleatorios. Aunque siempre se introduce un pequeño sesgo hacia 0 cuando se usa el exponente p-1.

Para generalizar este enfoque y ser más precisos, podemos tener una función 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)

¿Se permiten problemas de tarea aquí?

Esta función realiza matemática cruda "base 5" para generar un número entre 0 y 6.

function rnd7() {
    do {
        r1 = rnd5() - 1;
        do {
            r2=rnd5() - 1;
        } while (r2 > 1);
        result = r2 * 5 + r1;
    } while (result > 6);
    return result + 1;
}

Si consideramos la restricción adicional de tratar de dar la respuesta más eficiente, es decir, una que da un flujo de entrada I, de enteros distribuidos uniformemente de longitud mde 1 a 5 salidas, un flujo Ode enteros distribuidos uniformemente de 1 a 7 de la longitud relativa más larga a m, por ejemplo L(m).

La forma más sencilla de analizar esto es tratar los flujos I y Ocomo números 5-ary y 7-ary respectivamente. Esto se logra mediante la idea de la respuesta principal de tomar la transmisión a1, a2, a3,... -> a1+5*a2+5^2*a3+..y de manera similar para la transmisión O.

Luego, si tomamos una sección de la secuencia de entrada de longitud m choose n s.t. 5^m-7^n=cdonde c>0y es lo más pequeña posible. Luego hay un mapa uniforme de la secuencia de entrada de longitud m a enteros de 1a 5^my otra correspondencia uniforme de enteros de 1 7^na la secuencia de salida de longitud n donde es posible que tengamos que perder algunos casos de la secuencia de entrada cuando el entero asignado supera 7^n.

Entonces esto da un valor L(m)de alrededor de lo m (log5/log7)cual es aproximadamente .82m.

La dificultad con el análisis anterior es la ecuación 5^m-7^n=cque no es fácil de resolver con exactitud y el caso en que el valor uniforme desde 1que 5^mexcede 7^ny perder eficiencia.

La pregunta es qué tan cerca se puede alcanzar el mejor valor posible de m (log5 / log7). Por ejemplo, cuando este número se aproxima a un número entero, ¿podemos encontrar una manera de lograr este número entero exacto de valores de salida?

Si 5^m-7^n=ca continuación de la corriente de entrada que generamos efectivamente un número aleatorio uniforme de 0a (5^m)-1y no utilizamos cualquier valor más alto que 7^n. Sin embargo, estos valores pueden ser rescatados y utilizados nuevamente. Generan efectivamente una secuencia uniforme de números del 1 al 5^m-7^n. Entonces podemos intentar usarlos y convertirlos en números de 7 arios para poder crear más valores de salida.

Si dejamos T7(X)que sea la longitud promedio de la secuencia de salida de random(1-7)enteros derivados de una entrada uniforme de tamaño X, y suponiendo eso 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.

Entonces, T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)dado que tenemos una longitud sin secuencia con probabilidad 7 ^ n0 / 5 ^ m con un residual de longitud 5^m-7^n0con probabilidad (5^m-7^n0)/5^m).

Si seguimos sustituyendo obtenemos:

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

Por lo tanto

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

Otra forma de decir esto es:

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)

El mejor caso posible es mi original sobre dónde 5^m=7^n+s, dónde s<7.

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

El peor de los casos es cuando solo podemos encontrar k y st 5 ^ m = kx7 + s.

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

Otros casos están en algún punto intermedio. Sería interesante ver qué tan bien podemos hacerlo para m muy grande, es decir, qué tan bueno podemos obtener el término de error:

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

Parece imposible de lograr e(m) = o(1)en general, pero esperamos poder demostrarlo e(m)=o(m).

Todo se basa en la distribución de los dígitos de 7 arios de 5^mvarios valores de m.

Estoy seguro de que hay mucha teoría por ahí que cubre esto, puedo echar un vistazo e informar en algún momento.

Aquí hay una implementación de Python en funcionamiento de la respuesta 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

Me gusta lanzar algoritmos que estoy viendo en Python para poder jugar con ellos, pensé en publicarlo aquí con la esperanza de que sea útil para alguien allá afuera, no es que me tomó mucho tiempo armarlo.

¿Por qué no hacerlo simple?

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

Las posibilidades de obtener 1 y 7 en esta solución son menores debido al módulo, sin embargo, si solo desea una solución rápida y legible, este es el camino a seguir.

Suponiendo que rand (n) aquí significa "entero aleatorio en una distribución uniforme de 0 a n-1 ", aquí hay una muestra de código usando randint de Python, que tiene ese efecto. Utiliza solo randint (5) y constantes para producir el efecto de randint (7) . Un poco tonto, en realidad

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

La premisa detrás de la respuesta correcta de Adam Rosenfield es:

• x = 5 ^ n (en su caso: n = 2)
• manipule n llamadas rand5 para obtener un número y dentro del rango [1, x]
• z = ((int) (x / 7)) * 7
• si y> z, intente nuevamente. más retorno y% 7 + 1

Cuando n es igual a 2, tiene 4 posibilidades de descarte: y = {22, 23, 24, 25}. Si usa n es igual a 6, solo tiene 1 descarte: y = {15625}.

5 ^ 6 = 15625
7 * 2232 = 15624

Llamas a rand5 más veces. Sin embargo, tiene muchas menos posibilidades de obtener un valor de descarte (o un bucle infinito). Si hay una manera de no obtener un valor de descarte posible para y, todavía no lo he encontrado.

Aquí está mi respuesta:

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

Es un poco más complicado que otros, pero creo que minimiza las llamadas a rand5. Al igual que con otras soluciones, existe una pequeña probabilidad de que se pueda repetir durante mucho tiempo.

Simple y eficiente:

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

(Inspirado en ¿Cuál es tu dibujo animado favorito de "programador"? ).

Mientras no queden siete posibilidades para elegir, dibuje otro número aleatorio, que multiplique el número de posibilidades por cinco. En 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;
}

No me gustan los rangos que comienzan desde 1, así que comenzaré desde 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;
}

Ahí tienes, distribución uniforme y cero llamadas rand5.

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

Necesidad de establecer semillas de antemano.

Sé que ha sido respondido, pero parece que esto funciona bien, pero no puedo decirte si tiene un sesgo. Mi 'prueba' sugiere que es, al menos, razonable.

¿Quizás Adam Rosenfield sería tan amable de comentar?

Mi idea (ingenua) es esta:

Acumula rand5's hasta que haya suficientes bits aleatorios para hacer un rand7. Esto toma como máximo 2 rand5's. Para obtener el número rand7, uso el valor acumulado mod 7.

Para evitar que el acumulador se desborde, y dado que el acumulador es mod 7, entonces tomo el mod 7 del acumulador:

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

La función rand7 () sigue:

(Dejé que el rango de rand5 sea 0-4 y rand7 también sea 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;
}

Editar: Resultados agregados para 100 millones de ensayos.

Funciones rand 'reales' mod 5 o 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

Mi rand7

El promedio se ve bien y las distribuciones de números también se ven bien.

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

Hay algoritmos elegantes citados anteriormente, pero aquí hay una forma de abordarlo, aunque podría ser indirecto. Asumo valores generados a partir de 0.

R2 = generador de números aleatorios que proporciona valores inferiores a 2 (espacio muestral = {0, 1})
R8 = generador de números aleatorios que proporciona valores inferiores a 8 (espacio muestral = {0, 1, 2, 3, 4, 5, 6, 7 })

Para generar R8 a partir de R2, ejecutará R2 tres veces y utilizará el resultado combinado de las 3 ejecuciones como un número binario con 3 dígitos. Aquí está el rango de valores cuando R2 se ejecuta tres veces:

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

Ahora para generar R7 a partir de R8, simplemente ejecutamos R7 nuevamente si devuelve 7:

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

La solución indirecta es generar R2 a partir de R5 (al igual que generamos R7 a partir de R8), luego R8 a partir de R2 y luego R7 a partir de R8.

Aquí hay una solución que se ajusta completamente a enteros y está dentro de aproximadamente el 4% de lo óptimo (es decir, usa 1.26 números aleatorios en {0..4} para cada uno en {0..6}). El código está en Scala, pero las matemáticas deben ser razonablemente claras en cualquier idioma: aprovecha el hecho de que 7 ^ 9 + 7 ^ 8 está muy cerca de 5 ^ 11. Por lo tanto, elige un número de 11 dígitos en la base 5 y luego lo interpreta como un número de 9 dígitos en la base 7 si está dentro del rango (dando 9 números de base 7), o como un número de 8 dígitos si está por encima del 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)
  }
}

Si pega una prueba en el intérprete (REPL en realidad), obtiene:

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

La distribución es agradable y plana (dentro de aproximadamente 10k de 1/7 de 10 ^ 8 en cada contenedor, como se esperaba de una distribución aproximadamente gaussiana).

Al usar un total rodante , ambos pueden

• mantener una distribución equitativa; y
• No tiene que sacrificar ningún elemento en la secuencia aleatoria.

Ambos problemas son un problema con las rand(5)+rand(5)...soluciones de tipo simplista . El siguiente código de Python muestra cómo implementarlo (la mayor parte de esto es probar la distribución).

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)

Y esta salida muestra los 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%)

Una simplista rand(5)+rand(5), ignorando aquellos casos en los que esto devuelve más de 6 tiene una variación típica del 18%, 100 veces la del método que se muestra arriba:

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

Y, siguiendo los consejos de Nixuz, he limpiado el script para que pueda extraer y usar las rand7...cosas:

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)

Esta respuesta es más un experimento para obtener la mayor entropía posible de la función Rand5. Por lo tanto, no está claro y es casi seguro que es mucho más lento que otras implementaciones.

Suponiendo la distribución uniforme de 0-4 y la distribución 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;
  }
}

El número de bits agregados al búfer por llamada a Rand5 es actualmente 4/5 * 2, entonces 1.6. Si se incluye el valor de probabilidad de 1/5 que aumenta en 0.05, entonces 1.65, pero vea el comentario en el código donde he tenido que desactivar esto.

Bits consumidos por llamada a Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
Esto es 3 + 3/8 + 3/64 + 3/512 ... entonces aproximadamente 3,42

Al extraer información de los sietes, reclamo 1/8 * 1/7 bits por llamada, por lo que aproximadamente 0.018

Esto proporciona un consumo neto de 3,4 bits por llamada, lo que significa que la proporción es de 2.125 llamadas a Rand5 por cada Rand7. El óptimo debe ser 2.1.

Me imagino que este enfoque es significativamente más lento que muchos de los otros aquí a menos que el costo de la llamada a Rand5 sea extremadamente costoso (por ejemplo, llamar a alguna fuente externa de entropía).

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

realiza un bucle para producir un número aleatorio entre 16 y 127, se divide por dieciséis para crear un flotante entre 1 y 7.9375, luego se redondea hacia abajo para obtener un int entre 1 y 7. Si no me equivoco, hay una probabilidad de 16/112 de obtener cualquiera de los 7 resultados.

extern int r5();

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

Creo que tengo cuatro respuestas, dos que dan soluciones exactas como la de @Adam Rosenfield pero sin el problema del bucle infinito, y otras dos con una solución casi perfecta pero una implementación más rápida que la primera.

La mejor solución exacta requiere 7 llamadas a rand5 , pero procedamos para entender.

Método 1 - Exacto

La fortaleza de la respuesta de Adam es que proporciona una distribución uniforme perfecta, y hay una probabilidad muy alta (21/25) de que solo se necesiten dos llamadas a rand5 (). Sin embargo, el peor de los casos es el bucle infinito.

La primera solución a continuación también ofrece una distribución uniforme perfecta, pero requiere un total de 42 llamadas a rand5 . No hay bucles infinitos.

Aquí hay una implementación de 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 las personas que no están familiarizadas con R, aquí hay una versión 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
}

La distribución de rand5será preservada. Si hacemos los cálculos, cada una de las 7 iteraciones del ciclo tiene 5 ^ 6 combinaciones posibles, por lo tanto, el número total de combinaciones posibles es (7 * 5^6) %% 7 = 0. Por lo tanto, podemos dividir los números aleatorios generados en grupos iguales de 7. Vea el método dos para más discusión sobre esto.

Aquí están todas las combinaciones posibles:

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 

Creo que es sencillo demostrar que el método de Adam se ejecutará mucho más rápido. La probabilidad de que haya 42 o más llamadas rand5en la solución de Adam es muy pequeña ((4/25)^21 ~ 10^(-17) ).

Método 2: no exacto

Ahora el segundo método, que es casi uniforme, pero requiere 6 llamadas a rand5:

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

Aquí hay una versión simplificada:

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

Esto es esencialmente una iteración del método 1. Si generamos todas las combinaciones posibles, aquí están los conteos 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

Un número aparecerá una vez más en las 5^6 = 15625pruebas.

Ahora, en el Método 1, al sumar 1 a 6, movemos el número 2233 a cada uno de los puntos sucesivos. Por lo tanto, el número total de combinaciones coincidirá. Esto funciona porque 5 ^ 6 %% 7 = 1, y luego hacemos 7 variaciones apropiadas, entonces (7 * 5 ^ 6 %% 7 = 0).

Método 3 - Exacto

Si se entiende el argumento de los métodos 1 y 2, sigue el método 3 y solo requiere 7 llamadas a rand5. En este punto, siento que esta es la cantidad mínima de llamadas necesarias para una solución exacta.

Aquí hay una implementación de R:

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

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

Para las personas que no están familiarizadas con R, aquí hay una versión simplificada:

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

La distribución de rand5será preservada. Si hacemos los cálculos, cada una de las 7 iteraciones del ciclo tiene 5 resultados posibles, por lo tanto, el número total de combinaciones posibles es(7 * 5) %% 7 = 0 . Por lo tanto, podemos dividir los números aleatorios generados en grupos iguales de 7. Vea el método uno y dos para más discusión sobre esto.

Aquí están todas las combinaciones posibles:

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 

Creo que es sencillo demostrar que el método de Adam seguirá funcionando más rápido. La probabilidad de que haya 7 o más llamadas rand5en la solución de Adam sigue siendo pequeña ( (4/25)^3 ~ 0.004).

Método 4: no exacto

Esta es una variación menor del segundo método. Es casi uniforme, pero requiere 7 llamadas a rand5, que es una adicional al método 2:

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

Aquí hay una versión simplificada:

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

Si generamos todas las combinaciones posibles, aquí están los conteos 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

Dos números aparecerán una vez menos en las 5^7 = 78125pruebas. Para la mayoría de los propósitos, puedo vivir con eso.

La función que necesita es rand1_7 () , escribí rand1_5 () para que pueda probarla y trazarla.

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