repetir positivos numeros numero negativos metodo generar cifras arreglo aleatorios aleatorio algorithm random puzzle

algorithm - positivos - Expandir un rango aleatorio de 1–5 a 1–7



numeros aleatorios negativos y positivos en java (30)

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

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 ejecutar en una CPU más lenta?

¿Se permiten problemas con la tarea aquí?

Esta función realiza cálculos básicos en "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; }

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

Supongamos que rand5 () devuelve uno de {0,1,2,3,4} con la misma distribución y el objetivo es el retorno {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 bucle puede generar en la variable max . Si el resultado es entre max% 7 y max-1, entonces el resultado se distribuye uniformemente en ese rango. Si no, usamos el resto, que es aleatorio entre 0 y máx.% 7-1, y otra llamada a rand () para hacer un nuevo número y un nuevo máximo. Entonces comenzamos de nuevo.

Edición: el número de veces esperado 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()

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 pueda funcionar durante mucho tiempo.

Aquí hay una implementación funcional de Python 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é que lo publicaría aquí con la esperanza de que sea útil para alguien, no que haya tardado mucho tiempo en juntarlos.

Esto es equivalente a la solución de Adam Rosenfield, pero puede ser un poco más claro para algunos lectores. Asume 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 así: imagínese imprimiendo esta matriz de doble dimensión en papel, pegándola a un tablero de dardos y lanzándole dardos al azar. 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 lanzando el dardo hasta que alcances un cero. Eso es lo que hace este código: los índices i y j seleccionan al azar una ubicación en el tablero de dardos, y si no obtenemos un buen resultado, seguimos lanzando dardos.

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

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, inténtalo de nuevo. si no devuelve y% 7 + 1

Cuando n es igual a 2, tiene 4 posibilidades de desecho: 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 una probabilidad mucho menor de obtener un valor de descarte (o un bucle infinito). Si hay una manera de obtener ningún valor de desecho posible para y, aún no lo he encontrado.

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

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 la aleatoriedad. Es decir, si considera que la aleatoriedad es un recurso precioso, queremos utilizar 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 2 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 el uso de la aleatoriedad, debemos usar los 2.32193 bits de entropía de cada llamada a rand5() , y aplicarlos a la generación de 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 base 2 a menos que se especifique lo contrario. rand5() devuelve números en el rango [0, 4], y se rand7() 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 (supongamos por un momento que realmente podríamos calcular y almacenar un número tan infinitamente preciso; lo arreglaremos más adelante). Podemos generar tal número generando sus dígitos en la base 5: seleccionamos el número aleatorio 0. a 1 a 2 a 3 ..., donde cada dígito a i es elegido por una llamada a rand5() . Por ejemplo, si nuestro RNG eligió un i = 1 para todo i , ignorando el hecho de que eso no es muy aleatorio, eso correspondería al número real 1/5 + 1/5 2 + 1/5 3 + .. . = 1/4 (suma de una serie geométrica).

Bien, hemos elegido un número real aleatorio entre 0 y 1. Ahora afirmo que dicho número aleatorio se distribuye de manera uniforme. 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 necesitamos probar que la probabilidad de que nuestro número se encuentre en un intervalo [ a , b ] es igual a longitud de ese intervalo, b - a . La prueba queda como un 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 aleatoriamente 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 la base 7, y luego cada dígito base 7 se corresponderá con 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. Al convertir 1/4 en base 7, obtenemos el decimal infinito 0.15151515 ..., así 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 tratamos solo una parte finita? En segundo lugar, ¿cómo lo convertimos a la base 7?

Una forma en que podemos 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 fraccionaria
  4. Goto paso 1

Para enfrentar 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 a rand5() dos veces y devolvió 1 en ambas ocasiones. 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() producidas, el número real aleatorio que estamos generando nunca será mayor que 0.12: siempre es cierto que 0.11 ≤ 0.11xyz ... <0.12.

Entonces, al rastrear el número actual hasta ahora, 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 k dígitos, entonces podemos emitir con seguridad los siguientes k dígitos, independientemente de ¡lo que es el flujo infinito de 5 dígitos de base, nunca afectarán a los siguientes k dígitos de la representación de base 7!

Y ese es el algoritmo: para generar la próxima salida de rand7() , generamos solo tantos dígitos de rand5() como necesitamos para asegurarnos de saber con certeza el valor del siguiente dígito en la conversión del número real aleatorio a la 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. El arnés de prueba llama a next(r7) 10000 veces para producir 10000 números aleatorios, y luego mide su distribución. Solo se usa matemática de enteros, por lo que los resultados son exactamente correctos.

También tenga en cuenta que los números aquí son muy grandes, muy rápidos. 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 bignum. Pero recuerde que mi objetivo era 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 llamadas log (7) / log (5) en promedio a 4 cifras significativas, y la salida resultante fue uniforme.

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

No hay una solución (exactamente correcta) que se ejecutará 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 realizar un bucle para siempre.

Si consideramos la restricción adicional de tratar de dar la respuesta más eficiente, es decir, una dada un flujo de entrada, I , de enteros distribuidos uniformemente de longitud m de 1 a 5, sale un flujo O , de enteros distribuidos uniformemente de 1 a 7 de longitud más larga en relación con m , digamos L(m) .

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

Luego, si tomamos una sección del flujo de entrada de longitud m choose n st 5^m-7^n=c donde c>0 y sea lo más pequeño posible. Luego hay un mapa uniforme desde el flujo de entrada de longitud m hasta números enteros de 1 a 5^m y otro mapa uniforme desde números enteros de 1 hasta 7^n hasta el flujo de salida de longitud n, donde es posible que tengamos que perder algunos casos de el flujo de entrada cuando el entero mapeado excede 7^n .

Entonces, esto da un valor para L(m) de alrededor de m (log5/log7) que es aproximadamente .82m .

La dificultad con el análisis anterior es la ecuación 5^m-7^n=c que no es fácil de resolver exactamente y el caso en que el valor uniforme de 1 a 5^m supera los 7^n y perdemos eficiencia.

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

Si 5^m-7^n=c , desde el flujo de entrada generamos efectivamente un número aleatorio uniforme de 0 a (5^m)-1 y no usamos ningún valor superior a 7^n . Sin embargo, estos valores pueden ser rescatados y usados ​​nuevamente. Generan efectivamente una secuencia uniforme de números del 1 al 5^m-7^n . Entonces podemos tratar de usarlos y convertirlos en números 7-arios para poder crear más valores de salida.

Si permitimos que T7(X) sea ​​la longitud promedio de la secuencia de salida de enteros random(1-7) derivados de una entrada uniforme de tamaño X , y suponiendo que 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) ya que tenemos una longitud sin secuencia con probabilidad 7 ^ n0 / 5 ^ m con un residual de longitud 5^m-7^n0 con 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 poner 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 arriba, donde 5^m=7^n+s , donde s<7 .

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

El peor caso 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 lugar intermedio. Sería interesante ver qué tan bien podemos hacer para una 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 lograr e(m) = o(1) en general, pero esperamos poder probar que e(m)=o(m) .

Todo esto luego se basa en la distribución de los 7 dígitos de 5^m para varios valores de m .

Estoy seguro de que hay una gran cantidad de teorías que cubren esto. Puedo echar un vistazo e informar en algún momento.

Suponiendo que rand (n) aquí significa "entero aleatorio en una distribución uniforme de 0 a n-1 ", aquí hay un ejemplo de código que utiliza el código 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

Algoritmo:

7 pueden representarse en una secuencia de 3 bits

Utilice rand (5) para rellenar aleatoriamente cada bit con 0 o 1.
Por ejemplo: llamar a 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, 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 de 1-7.

EDITAR: Esta parece ser la respuesta más simple y eficiente, así que aquí hay algo de 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; } } }

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

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

Necesito poner semillas de antemano.

No me gustan los rangos 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; }

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

los bucles para producir un número aleatorio entre 16 y 127, se divide por dieciséis para crear un flotador entre 1 y 7.9375, luego se redondea 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.

simplemente escala tu salida desde tu primera función

0) you have a number in range 1-5 1) subtract 1 to make it in range 0-4 2) multiply by (7-1)/(5-1) to make it in range 0-6 3) add 1 to increment the range: Now your result is in between 1-7

Aquí hay una solución que encaja completamente dentro de enteros y está dentro de aproximadamente el 4% de lo óptimo (es decir, utiliza 1.26 números aleatorios en {0..4} para cada uno en {0..6}). El código está en Scala, pero los cálculos deben ser razonablemente claros en cualquier idioma: aproveche el hecho de que 7 ^ 9 + 7 ^ 8 está muy cerca de 5 ^ 11. Así que 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á en el rango (dando 9 números de base 7), o como un número de 8 dígitos si está sobre el 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), obtendrá:

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 bandeja, como se espera de una distribución aproximadamente gaussiana).

Esta respuesta es más un experimento para obtener la mayor entropía posible de la función Rand5. Por lo tanto, es algo poco claro y, casi con certeza, 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 de 4/5 * 2, por lo que 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 tuve que deshabilitar esto.

Bits consumidos por la llamada a Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
Esto es 3 + 3/8 + 3/64 + 3/512 ... así que aprox. 3,42

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

Esto da un consumo neto de 3,4 bits por llamada, lo que significa que la relació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 caro (por ejemplo, llamar a alguna fuente externa de entropía).

Hay algoritmos elegantes citados anteriormente, pero aquí hay una forma de abordarlo, aunque podría ser una rotonda. Estoy asumiendo valores generados desde 0.

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

Para generar R8 a partir de R2, ejecutará R2 tres veces y usará 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 de la rotonda es generar R2 desde R5 (al igual que generamos R7 desde R8), luego R8 desde R2 y luego R7 desde R8.

La función que necesitas es rand1_7 () , escribí rand1_5 () para que puedas 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

Mediante el uso de un total rodante , puede tanto

  • mantener una distribución equitativa; y
  • No hay 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ía de esto está demostrando 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%)

Un simplista rand(5)+rand(5), ignorando aquellos casos en que este retorna más de 6 tiene una variación típica de 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 el rand7...material:

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)

Mientras no haya 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; }

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

Tal vez Adam Rosenfield sería tan amable de comentar?

Mi idea (¿ingenua?) Es esta:

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

Para evitar el desbordamiento del acumulador, y dado que el acumulador es el mod 7, 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 es igualmente 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; }

Edición: Resultados agregados por 100 millones de intentos.

Funciones de rand ''real'' 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

Mi rand7

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

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

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

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

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, hace 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 números de manera aleatoria y uniforme de 0 a 15,624 y luego tomar el mod 7, podemos obtener un generador de rand7 casi uniforme. Los números del 0 al 15,624 pueden generarse uniformemente al rodar 5 rand 6 veces y usarlos 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

Asi que

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

se convierte en

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

Así que 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.

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: Eso no funciona del todo. Está apagado por aproximadamente 2 partes en 1000 (suponiendo un rand5 perfecto). Los cubos consiguen:

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 añadidos

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 de maneras en que la output=x puede suceder dadas 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]