Есть ли способ сделать красивую и элегантную взвешенную перетасовку, используя стандартную библиотеку? Есть 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);
Если целью OP является перетасовка списка r элементов
таким образом, что для заданного списка весов w элемент a[i] с весом w[i] должен быть первым элементом списка случайное перемешивание r с вероятностью w[i]/sum(w).
Как указано на странице, на которую ссылается Северин Паппадё:
Взвешенная случайная перетасовка аналогична взвешенной случайной выборке из списка a без замены. То есть выбрать с вероятностью 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;
}
}
Живой пример ЗДЕСЬ.
if ( i )?
- person JHBonarius; 08.05.2018
std::next(first, i) будет O(n) (обратите внимание, что std::shuffle требует случайных итераторов), так что имело смысл оптимизировать этот крайний случай. Конечно, в таких случаях было бы лучше скопировать данные в вектор и вместо этого преобразовать его. В общем, согласен, это преждевременная оптимизация и, наверное, я ее уберу.
- person Bob__; 24.04.2019
