Weighted Probability Lottery

weighted_probability_lottery.cpp

double throwDice() {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0, 1);
    return dis(gen);
}

template<class T>
typename std::vector<T>::const_iterator lottery(
    const std::vector<T>& list,
    std::function<double(const T&)> probabilityAccessor)
{
    double denominator = 0;
    for (const auto& element : list) {
        denominator += probabilityAccessor(element);
    }
    double dice = throwDice();
    double probabilitySum = 0;
    for (auto element = list.begin(); element != list.end(); ++element) {
        probabilitySum += probabilityAccessor(*element) / denominator;
        if (probabilitySum > dice)
            return element;
    }

    return list.end();
}

int main() {
    struct WeightedElement {
        double probability;
        int elementIndex;
    };
    std::vector<WeightedElement> list = {
        {0.25, 1},
        {0.75, 2},
    };
    auto result = lottery<WeightedElement>(
        list,
        [](const WeightedElement& element) {
            return element.probability;
        });

    std::cout << result->elementIndex << std::endl;

    return 0;
}