с ++ 11 — C ++. Weighted std :: shuffle

Question

с ++ 11 — C ++. Weighted std :: shuffle

Есть ли способ сделать красивую и элегантную перетасовку с использованием стандартной библиотеки?
Есть 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);

5

c++c++11 random shuffle weighted

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

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

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

Взвешенная случайная перетасовка аналогична взвешенной случайной выборке из списка а без замены. То есть выбираем с вероятностью 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;
}
}

Живой пример ВОТ.

6