Seleção aleatória ponderada com e sem substituição

Em resposta a um desafio de programação, buscamos algoritmos eficientes para seleção aleatória ponderada de uma lista, com e sem substituição.

Seleção ponderada com substituição

Um método eficaz para seleção ponderada com substituição é o Método Alias. Esta técnica cria um conjunto de caixas de tamanhos iguais para cada elemento ponderado. Ao utilizar operações de bits, podemos indexar esses compartimentos de forma eficiente, sem recorrer à pesquisa binária. Cada compartimento armazena uma única porcentagem que representa o limite entre os elementos ponderados originais.

Considere o exemplo de cinco elementos com pesos iguais: (a, b, c, d, e).

Implementação do método Alias

1. Normalizar pesos: divida cada peso pelo total para somar 1,0.
2. Determine a menor potência de 2 maior ou igual ao número de elementos (aqui, 8).
3. Atribua uma partição vazia para cada elemento.

4. Repita as etapas a seguir até que todos os pesos sejam distribuídos:

   • Coloque o máximo do elemento com o menor peso restante em uma partição vazia.
   • Se uma partição não estiver preenchida, adicione o elemento restante mais pesado.

Para nosso exemplo, após várias iterações, temos a seguinte partição:

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

Seleção de tempo de execução

1. Gere um número aleatório entre 0 e 1.
2. Bitshift o número aleatório para encontrar o índice de partição.
3. Se a partição for dividida, use a parte decimal do número bitshift para decidir qual elemento retornar.

Seleção ponderada sem substituição

Enquanto algoritmos como o método do reservatório ponderado existe para seleção não ponderada sem substituição, este problema permanece sem solução.