Aquí hay un algoritmo, suponiendo que tiene un método rand (i) para generar un entero aleatorio en [1 … i] con igual probabilidad.
Primero, genere el primer entero en [1 … N] usando rand (N). ¿Cómo podemos seleccionar un segundo entero de [1 … N] con igual probabilidad que no sea igual al entero ya seleccionado? Hay dos maneras de hacer esto.
El primer método es simple pero no determinista. Genere otro entero aleatorio usando rand (N). Si es el mismo que el entero originalmente seleccionado, deséchelo e intente nuevamente. Esto no es determinista, pero se espera que dé una respuesta en no demasiados pasos. También podemos usar este método para encontrar enteros posteriores, pero el número esperado de veces que rand () tendrá que ejecutarse para obtener un número entero que aún no se haya visto seguirá aumentando. Esto sería especialmente un problema cuando K está muy cerca de N. Pero en ese caso, tiene más sentido elegir los números únicos NK para descartar al azar. Como min (K, NK) es como máximo N / 2, nunca tendremos más de N / 2 números para evitar al mirar la salida de rand (). Esto significa que cada vez, se espera que nuestro algoritmo termine en 2 pasos o menos. Como podemos usar una tabla hash para verificar si ya se ha elegido un número entero, el tiempo de ejecución general esperado del algoritmo es O (K). Aquí está el pseudocódigo:
- ¿Cuál es el código de búsqueda binaria usando recursividad?
- ¿Cómo eliminará elementos de manera eficiente mientras itera una Colección?
- Cómo resolver este problema de integración definitiva
- ¿Cómo se puede calcular su edad en días? Necesito el algoritmo más simplificado para resolverlo.
- Informática: ¿Cuál es el futuro de la investigación en algoritmos?
elegido = {}
para i = 1 a K:
hacer:
x = rand (N)
mientras x está en elegido
inserte x en elegido
fin
Existe un segundo método determinista. Supongamos que ya hemos elegido i enteros. Necesitamos elegir un número entero uniformemente entre los números enteros restantes de Ni. Para esto, genere un entero aleatorio x en el rango [1 … Ni] usando rand (Ni). Ahora podemos encontrar el número x no elegido en [1 … N]. Para esto, mantenga una matriz ordenada de números elegidos, digamos ar. Si el primer elemento de ar es mayor que x, x es el número x no elegido. De lo contrario, incremente x en 1 y mire la posición en ar. Continúe así hasta que la siguiente posición en ar contenga un número mayor que x (o hemos llegado al final de la matriz). Como hemos incrementado x en el número de posiciones sobre las que hemos saltado, hemos encontrado el x número no elegido según lo previsto. Dado que este paso puede llevar tiempo O (i), tiene sentido insertar x en la matriz ordenada utilizando la ordenación por inserción. Por lo tanto, la complejidad general del algoritmo es O (K ^ 2). Aquí está el pseudocódigo
ar [] = {}
para i = 0 a K-1
x = rand (Ni)
para pos = 0 a i-1:
si x> ar [pos]:
descanso
x + = 1
fin para
para j = i a pos + 1:
ar [j] = ar [j-1]
ar [pos] = x
fin
Si N es tan pequeño que una matriz de tamaño N cabe en la memoria, aquí hay un método mucho más fácil, en la línea de Knuth shuffle:
ar [] = {1 ... N}
para i = 0 a K-1:
intercambiar ar [Ni], ar [rand (Ni)]
fin
Esto es tanto determinista como O (N). Las últimas K posiciones en la matriz tendrán K enteros únicos elegidos de manera uniforme al azar.
