Pregunta Expandir un rango aleatorio de 1-5 a 1-7


Dada una función que produce un entero aleatorio en el rango de 1 a 5, escribe una función que produce 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 ejecutar en una CPU más lenta?

652


origen


Respuestas:


Esto es equivalente a la solución de Adam Rosenfield, pero puede ser un poco más claro para algunos lectores. 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: imagínense imprimir esta matriz de doble dimensión en papel, unirla a un tablero de dardos y arrojarle dardos al azar. Si tocas un valor distinto de cero, es un valor estadísticamente aleatorio entre 1 y 7, ya que hay una cantidad igual de valores distintos de cero para elegir. Si tocas un cero, sigue arrojando el dardo hasta que toques un valor distinto de cero. Eso es lo que hace este código: los índices iyj seleccionan aleatoriamente una ubicación en el tablero de dardos, y si no obtenemos un buen resultado, seguimos arrojando dardos.

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


530



No hay 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 usar el 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 infinitesimalmente pequeña de bucle para siempre.


328



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 a rand7(), para maximizar el uso de aleatoriedad. Es decir, si considera que la aleatoriedad es un recurso precioso, queremos utilizar la mayor cantidad de información posible, sin descartar ningún fragmento aleatorio. Esta respuesta también tiene algunas similitudes con la lógica presentada en La respuesta de Ivan.

los 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 log2 N. Por lo tanto, rand5() tiene aproximadamente 2.32193 bits de entropía, y rand7() tiene alrededor de 2.80735 bits de entropía. Si esperamos maximizar nuestro uso de la 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 registrar (7) / log (5) = 1.20906 llamadas a rand5() por llamada a rand7().

Notas al margen: todos los logaritmos en esta respuesta serán la base 2 a menos que se especifique lo contrario. rand5() se asumirá 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 infinitamente precisonúmero real aleatorio entre 0 y 1 (pretendemos por el momento que podríamos calcular y almacenar ese número infinitamente preciso, lo solucionaremos más adelante). Podemos generar dicho número generando sus dígitos en la base 5: seleccionamos el número aleatorio 0.a1a2a3..., donde cada dígito ai es elegido por una llamada a rand5(). Por ejemplo, si nuestro RNG eligió uni = 1 para todos i, ignorando el hecho de que no es muy aleatorio, eso correspondería al número real 1/5 + 1/52 + 1/53 + ... = 1/4 (suma de una serie geométrica).

Bien, hemos escogido un número real aleatorio entre 0 y 1. Ahora afirmo que ese número aleatorio está distribuido uniformemente. Intuitivamente, esto es fácil de entender, ya que cada dígito fue elegido 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 necesitamos demostrar que la probabilidad de que nuestro número se encuentre en un intervalo [a, b] es igual a la duración de ese intervalo, b - a. La prueba queda como ejercicio para el lector =).

Ahora que tenemos un número real aleatorio seleccionado uniformemente del rango [0, 1], necesitamos convertirlo en una serie de números uniformemente aleatorios en el rango [0, 6] para generar la salida de rand7(). Cómo hacemos esto? Justo al revés de lo que acabamos de hacer, lo convertimos en un decimal infinitamente preciso en la base 7, y luego cada dígito 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. Convirtiendo 1/4 a base 7, obtenemos el decimal infinito 0.15151515 ..., así que produciremos como salida 1, 5, 1, 5, 1, 5, etc.

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

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

  1. Multiplicar por 7
  2. La parte integral del resultado es la próxima base de 7 dígitos
  3. Reste la parte integral, dejando solo la parte fraccionaria
  4. Ir al paso 1

Para tratar el problema de la precisión infinita, calculamos un resultado parcial, y también almacenamos un límite superior en lo que podría ser el resultado. Es decir, supongamos que hemos llamado rand5() dos veces y devolvió 1 ambas veces. El número que hemos generado hasta ahora es 0.11 (base 5). Cualquiera que sea el resto de la serie infinita de llamadas a rand5() producir, 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, haciendo 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 la primera k dígitos, entonces podemos sacar de forma segura el siguiente kdígitos, independientemente de la corriente infinita de los 5 dígitos básicos, nunca afectarán a la siguiente k dí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 de rand5() ya que necesitamos asegurarnos de que sabemos con certeza el valor del siguiente dígito en la conversión del número real aleatorio a base 7. Aquí hay 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. Las llamadas de arnés de prueba next(r7) 10000 veces para producir 10000 números aleatorios, y luego mide su distribución. Solo se utilizan cálculos enteros, por lo que los resultados son exactamente correctos.

También tenga en cuenta que los números aquí obtienen muy grande, muy rápido. Los poderes 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 de bignum. Pero recuerde que mi objetivo fue maximizar el uso de bits aleatorios, no maximizar el rendimiento (aunque ese es un objetivo secundario).

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

Para portar este código a un idioma que no tenga integrados enteros arbitrariamente grandes, tendrá que limitar los valores de pow5 y pow7 al valor máximo de su tipo integral nativo: si crecen demasiado, reinicie todo y comience nuevamente. Esto aumentará la cantidad promedio de llamadas a rand5() por llamada a rand7() muy levemente, pero con suerte no debería aumentar demasiado incluso para enteros de 32 o 64 bits.


145



(He robado La respuesta de Adam Rosenfeld y lo hizo correr aproximadamente 7% más rápido).

Supongamos que rand5 () devuelve uno de {0,1,2,3,4} con distribución igual y el objetivo es return {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 haciendo un seguimiento del mayor valor que el bucle puede hacer en la variable max. Si el resultado hasta ahora está 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 máximo. Entonces comenzamos de nuevo.

Editar: Esperar el 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()

35



Algoritmo:

7 se puede representar en una secuencia de 3 bits

Usa rand (5) para llenar aleatoriamente cada bit con 0 o 1.
Por ejemplo: call rand (5) y

si el resultado es 1 o 2, llena el bit con 0
si el resultado es 4 o 5, llena el bit con 1
si el resultado es 3, ignore y vuelva a hacerlo (rechazo)

De esta forma podemos llenar 3 bits aleatoriamente con 0/1 y así obtener un número del 1-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;
        }
    }
}

25



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

19



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

15



rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Editar: Eso no funciona. Está desactivado en aproximadamente 2 partes en 1000 (suponiendo un rand perfecto5). 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 el número formas output=x puede suceder dado n llamadas 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]

15