El algoritmo más eficiente para imprimir 1-100 usando un generador de números aleatorios dado

11

Se nos da un generador de números aleatorios RandNum50que genera un entero aleatorio uniformemente en el rango 1-50. Podemos usar solo este generador de números aleatorios para generar e imprimir todos los enteros del 1 al 100 en un orden aleatorio. Cada número debe venir exactamente una vez, y la probabilidad de que ocurra cualquier número en cualquier lugar debe ser igual.

¿Cuál es el algoritmo más eficiente para esto?

Raj Wadhwa
fuente
1
Use un vector de matriz / bit para registrar los números ya vistos y un contador para registrar el número de números únicos vistos.
Dave Clarke
@DaveClarke ¿Cómo puedo generar un número mayor que 50 con eso? Si lo uso más de 1 vez, entonces también, ¿cómo generaré 1 usándolos?
Raj Wadhwa
1
El desafío, por supuesto, es garantizar que todos los lugares ocurran con la misma probabilidad. Podrías usar RandNum100 = (RandNum50() * 2) - (RandNum50 > 25) ? 0 : 1).
Dave Clarke
2
@DaveClarke: ¿Entonces propone un muestreo de rechazo iterado? Eso terminaría solo en la expectativa.
Raphael
Simplemente estaba dando una pista.
Dave Clarke el

Respuestas:

3

Pensé (por lo que puede estar equivocado :-) de esta solución que usa el shuffle de Fisher-Yates . Para mantener una distribución uniforme con una buena aproximación (consulte la sección EDITAR a continuación) en cada iteración, puede usar este truco para producir un valor entre 0 y k - 1 :O(N2)krand0k1

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {    
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

El algoritmo de Fisher-Yates se convierte en:

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

EDITAR:

krandm=log2(k)rk

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits        
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }      
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}
Vor
fuente
1
O(n)
1
Creo que "barajar" es la palabra clave aquí.
Raphael
44
El truco en krand (k) no produce una distribución verdaderamente uniforme, aunque es una buena aproximación: incluso para k = 3, esto da una probabilidad del 33.333328% de generar 0. ¿Hay alguna justificación para sumar hasta k aquí? ? Creo que un límite más pequeño es suficiente si solo queremos una aproximación.
Erick Wong
1
@ErickWong: tienes razón; Creo que la verdadera distribución uniforme solo se puede alcanzar utilizando el método de muestreo de rechazo que no se garantiza que termine en tiempo constante. Existen otros esquemas de aproximación (que permiten alcanzar cualquier aproximación deseada), el que propuse es el primero que se me ocurrió.
Vor
2
r1..100rr
4

Dado que otras personas han dado soluciones aproximadas y soluciones que implican tomar números indeterminados de desviaciones, ¿qué tal una prueba de que no existe tal algoritmo que garantice que solo requiera un número finito de RandNum50()llamadas?

1100!

kRandNum50kkRandNum50kkRandNum50(r1,r2,,rk)150kc50kc1100!100!50kk100!50k

Steven Stadnicki
fuente
2

nlogn+O(1)

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

1n!123n

Si no sabe cómo generar un uniforme, como se sugiere en esa publicación, a partir de un bit aleatorio, también podría generar una aproximación del uniforme directamente, de esta manera (que es equivalente al "verdadero y" de Vor, pero más rápido):

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

P50Pn = 100 ! P > nQ=Pmodnn=100!P>n

Jérémie
fuente
1

No he hecho el análisis para confirmar qué tan uniforme (o no) sería esto, y podría ajustarse para que sea una mezcla aleatoria verdadera, pero ¿podría elegir, desde una matriz inicial del iíndice th = i + 1, el (k + RandNum50() + RandNum50() - 1) mod (100 - k)índice, con eliminación, para k= 0..99?

Esto "empuja" el pico en la RandNum50() + RandNum50()distribución hacia adelante de manera uniforme.

Estoy bastante seguro de que esto no es del todo correcto, ya que lo he dicho porque el índice 0 (1) no se puede obtener de la primera opción y no puedo ver rápidamente un ajuste alternativo 1..50 + 1..50 que produzca 0 ..99.

Actualizar

Para solucionar el problema que noté, utilicé efectivamente RandNum100como se menciona en los comentarios de la pregunta para inicializar aleatoriamente el primer kdesplazamiento.

Esto produce una distribución con una onda significativa en el frente.

En lugar de avanzar por 1, usé otro RandNum50para incrementar eso primero k. Esto produce un resultado que es lo suficientemente aleatorio para mí, pero todavía no es "verdaderamente" aleatorio, como se puede ver fácilmente si cambia K a 2.

Probar el código VB.NET donde atendí a cualquier K. Tenga en cuenta que es O (K), 6K + 2, de hecho.

Mark Hurd
fuente