How Can We Implement Weighted Random Selection with and Without Replacement?

Weighted Random Selection with and Without Replacement: A Comprehensive Guide

Selecting elements from a list with specific weights can be a valuable technique in various applications. While weighted selection without replacement has well-established algorithms, selecting elements with replacement poses a different challenge.

One efficient method for weighted selection with replacement is the Alias Method. By normalizing weights to sum up to 1.0 and finding the smallest power of 2 greater than the number of choices, partitions can be created for each variable. The method iteratively fills partitions with the least and most weighted variables, assigning the remaining weight from the original partition as necessary.

At runtime, a uniform random number is generated, and its binary representation is shifted by the log of the number of partitions. The index of the selected partition is determined by the shifted number. If the partition is split, the decimal portion of the shifted random number determines the selection between the two variables assigned to that partition.

The Alias Method is known for its efficiency, relying on simple algebraic operations and constant-time indexing. It allows for efficient selection even when a significant fraction of the list needs to be selected, making it a suitable choice for various scenarios where weighted random selection with replacement is required.

The above is the detailed content of How Can We Implement Weighted Random Selection with and Without Replacement?. For more information, please follow other related articles on the PHP Chinese website!