// Copyright 2017 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "absl/random/discrete_distribution.h"
namespace absl {
namespace random_internal {
// Initializes the distribution table for Walker's Aliasing algorithm, described
// in Knuth, Vol 2. as well as in https://en.wikipedia.org/wiki/Alias_method
std::vector<std::pair<double, size_t>> InitDiscreteDistribution(
std::vector<double>* probabilities) {
// The empty-case should already be handled by the constructor.
assert(probabilities);
assert(!probabilities->empty());
// Step 1. Normalize the input probabilities to 1.0.
double sum = std::accumulate(std::begin(*probabilities),
std::end(*probabilities), 0.0);
if (std::fabs(sum - 1.0) > 1e-6) {
// Scale `probabilities` only when the sum is too far from 1.0. Scaling
// unconditionally will alter the probabilities slightly.
for (double& item : *probabilities) {
item = item / sum;
}
}
// Step 2. At this point `probabilities` is set to the conditional
// probabilities of each element which sum to 1.0, to within reasonable error.
// These values are used to construct the proportional probability tables for
// the selection phases of Walker's Aliasing algorithm.
//
// To construct the table, pick an element which is under-full (i.e., an
// element for which `(*probabilities)[i] < 1.0/n`), and pair it with an
// element which is over-full (i.e., an element for which
// `(*probabilities)[i] > 1.0/n`). The smaller value can always be retired.
// The larger may still be greater than 1.0/n, or may now be less than 1.0/n,
// and put back onto the appropriate collection.
const size_t n = probabilities->size();
std::vector<std::pair<double, size_t>> q;
q.reserve(n);
std::vector<size_t> over;
std::vector<size_t> under;
size_t idx = 0;
for (const double item : *probabilities) {
assert(item >= 0);
const double v = item * n;
q.emplace_back(v, 0);
if (v < 1.0) {
under.push_back(idx++);
} else {
over.push_back(idx++);
}
}
while (!over.empty() && !under.empty()) {
auto lo = under.back();
under.pop_back();
auto hi = over.back();
over.pop_back();
q[lo].second = hi;
const double r = q[hi].first - (1.0 - q[lo].first);
q[hi].first = r;
if (r < 1.0) {
under.push_back(hi);
} else {
over.push_back(hi);
}
}
// Due to rounding errors, there may be un-paired elements in either
// collection; these should all be values near 1.0. For these values, set `q`
// to 1.0 and set the alternate to the identity.
for (auto i : over) {
q[i] = {1.0, i};
}
for (auto i : under) {
q[i] = {1.0, i};
}
return q;
}
} // namespace random_internal
} // namespace absl
