Перемешайте, чтобы охватить все возможные перестановки

Объект Random в .NET framework принимает 32-битное целое число в качестве начального значения. Это означает, что любой алгоритм перетасовки, использующий объект Random, ограничен (максимум) 4 миллиардами возможных перетасовок (при условии, что перетасовка является детерминированной в соответствии со случайной последовательностью, и я не могу представить, почему это не так). Это означает, что когда коллекция превышает 13 элементов, гарантируется, что перетасовка не охватит все возможные перестановки. По мере того, как размер коллекции становится все дальше от этого размера, подмножество возможных перестановок, охватываемых перетасовкой, становится все более и более незначительным.

4 миллиарда - это (субъективно) большое число, но если вы создаете несколько «случайных» перестановок коллекции, вероятность дублирования становится намного больше, чем должна быть (особенно, если вы рассматриваете парадокс дня рождения / принцип ящика).

Есть ли какой-нибудь простой способ обойти это, не требуя от меня реализации собственного генератора случайных чисел?


.net random c# algorithm shuffle
person Patrick M    schedule 01.07.2014    source источник
comment
Интересно, поэтому в лучшем случае покрытие будет 4bil^n, где n — количество раз, которое я тасую. Единственная проблема заключается в том, что если перемешивание происходит очень быстро, мне может потребоваться заснуть на миллисекунду, чтобы убедиться, что семя отличается.   -  person Patrick M    schedule 01.07.2014
comment
Вы можете рассмотреть возможность использования онлайн-API Random.org для генерации случайных чисел, если ваше приложение/проект подходит для этого; просто мои два цента.   -  person Lexicon    schedule 01.07.2014
comment
Если вы используете это, например. в игровых целях вам, вероятно, следует переключиться на криптографически безопасный ГСЧ.   -  person Damien_The_Unbeliever    schedule 01.07.2014
comment
Разделяй и властвуй: int digitNum = 10; длинный л = 0; Random r = new Random (DateTime.Now.Millisecond); for (int i = 0; i ‹ digitNum; i++) l += r.Next(0, 9) * (long)Math.Pow((double)10, (double)i);   -  person Johnny    schedule 01.07.2014
comment
Обратите внимание, что DateTime.Millisecond может меняться только каждые несколько миллисекунд, в зависимости от системы.   -  person Matthew Watson    schedule 01.07.2014
comment
разве алгоритм перетасовки Фишера-Йейтса не решит вашу проблему?   -  person Felice Pollano    schedule 01.07.2014
comment
ericlippert.com/2013/05/06/production-permutations-part -семь. Если подумать, вы должны прочитать всю серию, начиная с ericlippert. .com/2013/04/15/production-permutations-part-one. В нем он показывает, как превратить случайное число в перестановку.   -  person Jim Mischel    schedule 01.07.2014

Ответы (2)


arrow_upward
1
arrow_downward

Я бы не рекомендовал создавать собственный генератор случайных чисел (ГСЧ). Теория, стоящая за ними, довольно прочная. Если вам нужно что-то «более случайное», вам нужно использовать криптографически безопасный ГСЧ. Чтобы использовать генератор по умолчанию, предоставляемый платформой .Net:

использование System.Security.Cryptography;

var генератор = RandomNumberGenerator.Create();

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

person Ananke    schedule 01.07.2014

arrow_upward
0
arrow_downward

Вы можете использовать один из свободно доступных перенос Mersenne Twister на C#. MT19937 имеет 19937-битное пространство состояний, и, хотя вы можете выбрать заполнение его одним целым, также доступно полное заполнение состояния, если у вас есть подходящий источник энтропии, из которого он загружается.

person pjs    schedule 01.07.2014