How Can I Generate Weighted Random Numbers Using the Boost Library?

Weighted Random Numbers in Boost

The Boost library provides extensive random number generation functionality. While it offers simple random number generation, it lacks built-in support for weighted random numbers. This article explores techniques for implementing weighted random number picking using raw Boost functions.

Weighted Randomization Algorithm

To generate a weighted random number, we can employ the following algorithm:

1. Calculate the sum of all weights.
2. Generate a random number between 0 and the sum of weights (inclusive).
3. Iteratively subtract weights from the random number until it becomes negative. The index of the current item is the selected weighted number.

Adaptation to Boost

This algorithm can be adapted to Boost as follows:

using namespace boost;

int weightedRandom(const std::vector<int>& weights) {
  // Calculate the sum of weights
  int sum = accumulate(weights.begin(), weights.end(), 0);

  // Generate a random number between 0 and the sum
  variate_generator<mt19937, uniform_int_distribution<int>> rand(generator());
  int rnd = rand(sum);

  // Traverse weights and subtract until random number becomes negative
  for (size_t i = 0; i < weights.size(); ++i) {
    if (rnd - weights[i] < 0) {
      return i;
    }
    rnd -= weights[i];
  }

  // Should never reach here
  assert(false);
}

Optimization for Unchanging Weights

If weights are rarely changed and the list is reasonably long, we can optimize by precomputing cumulative weight sums and using binary search.

Reservoir Sampling for Unknown List Size

For lists with unknown size, reservoir sampling can be employed with weighted adaptations.

Conclusion

While Boost lacks a dedicated weighted random number function, the presented techniques enable efficient and accurate generation using raw Boost functions.

The above is the detailed content of How Can I Generate Weighted Random Numbers Using the Boost Library?. For more information, please follow other related articles on the PHP Chinese website!