Ошибка при перетасовке вектора с boost::random

Question

Я использую этот код для генерации случайной перестановки вектора с использованием вариации алгоритма рандомизации Фишера-Йейтса (я иду от первого элемента к последнему, а не наоборот). Я использую boost::random::mt11213b ГСЧ в глобальном масштабе в программе, которая generator.seed(time(NULL)); когда программа запускается, следовательно, обертка синглтон RandomNumber Вот.

boost::random::uniform_int_distribution<unsigned long> 
    distribution(0, vec.size()-1);

for (unsigned long i=0;i<vec.size();i++)
    std::swap(vec[i], vec[distribution(RandomNumber::getInstance().generator)]);

Некоторые эксперименты привели меня к мысли, что, в двух словах, в этом алгоритме может быть проблема. Это то что я сделал

1. Создан вектор целого числа длиной 100
2. Заполнены первые 75 элементов 0 и последние 25 с 1
3. Перетасовал массив.
4. Взял первые 5 элементов из списка и суммировал их.

Я повторил эту процедуру несколько тысяч раз (с циклом, а не вручную:)) каждый раз, начиная с нового вектора. Затем я вычислил среднее арифметическое сумм, и это произошло 0.98 вместо ожидаемого 1.25,

Самое смешное, что если я начну с вектора, который был перетасован один и тот же алгоритм вместо упорядоченного, результат возрастает до 1.22 и если я не отбрасываю вектор на каждой итерации, а просто перетасую его снова, результат будет примерно 1.25это ожидаемое значение.

Я не уверен, что может быть не так. Алгоритм выглядит хорошо, единственное, о чем я мог думать, что это могло пойти не так, это фаза посева и

boost::random::uniform_int_distribution<unsigned long> 
    distribution(0, vec.size()-1);

строка, которая вызывается каждый раз перед перетасовкой вектора (возможно, ее следует вызывать только один раз в программе, но это не имеет смысла)

Любая помощь будет оценена!

Answer 1

Если бы мне пришлось угадать причину, вы не меняете размер распределения каждый раз вокруг цикла. Алгоритм искусства компьютерного программирования здесь.

Как только вы перемешаете до n элементов, вы не хотите снова касаться первых n, потому что повторяющиеся применения псевдослучайных чисел не делают вещи более случайными, они делают их менее случайными.

Answer 2

Нет, ваш алгоритм неверен. Рассмотрим простой случай с вектором из 4 чисел, ваш алгоритм возвращает следующие смещенные результаты

result      probability * 256
{1,2,3,4}   10
{1,2,4,3}   10
{1,3,2,4}   10
{1,3,4,2}   14
{1,4,2,3}   11
{1,4,3,2}   9
{2,1,3,4}   10
{2,1,4,3}   15
{2,3,1,4}   14
{2,3,4,1}   14
{2,4,1,3}   11
{2,4,3,1}   11
{3,1,2,4}   11
{3,1,4,2}   11
{3,2,1,4}   9
{3,2,4,1}   11
{3,4,1,2}   11
{3,4,2,1}   10
{4,1,2,3}   8
{4,1,3,2}   9
{4,2,1,3}   9
{4,2,3,1}   8
{4,3,1,2}   10
{4,3,2,1}   10

Тогда как стандартный алгоритм Фишера-Йейтса даст одинаковую вероятность для всех результатов.

Если вы хотите перемешать вектор, используйте std::random_shuffle непосредственно (см. Использование boost:: random в качестве ГСЧ для std::random_shuffle для некоторых примеров кодов).