C ++. Weighted std :: shuffle

Question

Есть ли способ сделать красивую и элегантную перетасовку с использованием стандартной библиотеки? Есть std::discrete_distribution. Я хочу что-то вроде этого:

std::vector<T> data { N elements };
std::vector<int> weights { N weights };
std::shuffle(std::begin(data), std::end(data), something based on discrete distribution);

Answer 1

Если OP намерен перетасовать список r элементов

таким, что при заданном списке весов w элемент a [i] с весом w [i] должен быть первым элементом случайного перемешивания r с вероятностью w [i] / sum (w) .

Как указано на странице , связанной с Северин Паппадо :

Взвешенная случайная перетасовка такая же, каквзвешенная случайная выборка из списка а без замены.То есть выбираем с вероятностью w [i] / sum (w) элемент a [i] из a.Сохранить этот элемент в списке r.Затем удалите элемент a [i] из a и w [i] из w и выберите новый элемент измененного списка a и т. Д., Пока a не станет пустым.

Я не будуизвестно о таком алгоритме в стандартной библиотеке, но простой реализацией может быть:

#include <random>
#include <algorithm>
#include <iterator>

template <class D, class W, class URBG>
void weighted_shuffle
    ( D first, D last
    , W first_weight, W last_weight
    , URBG&& g )
{
    while (first != last and first_weight != last_weight)
    {
        std::discrete_distribution dd(first_weight, last_weight);
        auto i = dd(g);
        if ( i )
        {
            std::iter_swap(first, std::next(first, i));
            std::iter_swap(first_weight, std::next(first_weight, i));
        }
        ++first;
        ++first_weight;
    }
}

Живой пример ЗДЕСЬ .