What is a Suitable Approach for Weighted Random Selection With Replacement?

Weighted Random Selection: Overcoming Replacement Limitations

Recently, many developers have encountered the challenge of weighted random selection of elements from a list, both with and without replacement. While effective algorithms exist for unweighted selection and weighted selection without replacement, finding a suitable solution for weighted selection with replacement has proven difficult.

One innovative approach that achieves efficiency and simplicity is the alias method. It works by creating equal-sized bins for the weighted list. These bins are indexed efficiently using bit operations, avoiding time-consuming binary searches.

To form the alias lookup table:

1. Normalize weights to sum to 1.0 (e.g., from (1, 1, 1, 1, 1) to (0.2, 0.2, 0.2, 0.2, 0.2)).
2. Determine the smallest power of 2 greater than or equal to the number of variables and create that number of partitions. In our example of five choices, we would create eight partitions.
3. Assign the least remaining weight to an empty partition (e.g., partition 1 gets weight 0.075).
4. If the partition is not full, assign the most weight to it as well (e.g., partition 2 now has weights 0.075 and 0.15).

Repeat steps 3 and 4 until all original weight is assigned.

During runtime:

1. Generate a random number in the range [0, 1] (e.g., 0.001100000).
2. Shift the random number by log2(num_partitions) to find the relevant partition (e.g., 001.1 maps to partition 2).
3. If the partition is split, use the decimal portion of the shifted random number to decide the split.

This method effectively handles weighted random selection with replacement, providing a significant performance boost compared to reservoir-based approaches, especially when selecting a large portion of a list.

The above is the detailed content of What is a Suitable Approach for Weighted Random Selection With Replacement?. For more information, please follow other related articles on the PHP Chinese website!