Selección aleatoria ponderada con y sin reemplazo

En respuesta a un desafío de programación, buscamos algoritmos eficientes para la selección aleatoria ponderada de una lista, tanto con como sin reemplazo.

Selección ponderada con reemplazo

Un método eficaz para la selección ponderada con reemplazo es el Método de alias. Esta técnica crea un conjunto de contenedores del mismo tamaño para cada elemento ponderado. Al utilizar operaciones de bits, podemos indexar estos contenedores de manera eficiente sin recurrir a la búsqueda binaria. Cada contenedor almacena un único porcentaje que representa el límite entre los elementos ponderados originales.

Considere el ejemplo de cinco elementos con pesos iguales: (a, b, c, d, e).

Implementación del método de alias

1. Normalizar pesos: divide cada peso por el total para sumar 1,0.
2. Determina la potencia más pequeña de 2 mayor o igual que el número de elementos (aquí, 8).
3. Asigne una partición vacía a cada elemento.

4. Repita los siguientes pasos hasta que todos los pesos estén distribuidos:

   • Coloque la mayor cantidad posible del elemento con el menor peso restante en una partición vacía.
   • Si una partición no está llena, agregue el elemento restante más pesado.

Para nuestro ejemplo, después de varias iteraciones, tenemos la siguiente partición:

• p1: {a, 1.0}
• p2: {a, b, 0.6}

Selección de tiempo de ejecución

1. Genera un número aleatorio entre 0 y 1.
2. Desplace el número aleatorio para encontrar el índice de la partición.
3. Si la partición está dividida, use la porción decimal del número con desplazamiento de bits para decidir qué elemento devolver.

Selección ponderada sin reemplazo

Mientras los algoritmos Al igual que existe el método de depósito ponderado para la selección no ponderada sin reemplazo, este problema sigue sin resolverse.