Генерировать последовательность целых чисел в случайном порядке без построения всего списка upfront

Как я могу сгенерировать список целых чисел от 1 до N, но в случайном порядке, не создавая весь список в памяти?

(Чтобы быть ясным: каждое число в сгенерированном списке должно появляться только один раз, поэтому оно должно быть эквивалентно сначала созданию всего списка в памяти, а затем перетасовке.)

Это было определено как дубликат этого вопроса.

Ответы

Ответ 1

очень простой случайный случай равен 1 + ((мощность (r, x) -1) mod p) будет от 1 до p для значений x от 1 до p и будет случайным, где r и p - простые числа, а r < > p.

Ответ 2

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

Установите все N бит в 0, затем для каждого желаемого номера:

  • используйте один из обычных линейных конгруэнтных методов для выбора числа от 1 до N.
  • Если это число уже используется, найдите следующий самый высокий неиспользованный (0 бит) с оберткой.
  • установите бит числа в 1 и верните его.

Таким образом вам гарантируется только одно использование на число и относительно случайные результаты.

Ответ 3

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

Если вы находитесь в жестких условиях памяти, вы можете попробовать:

  • Сохраняйте полученные результаты в дереве, рандомизируйте данные и вставьте их в дерево. Если вы не можете вставить, сгенерируйте еще один номер и повторите попытку и т.д., Пока дерево не заполнится на полпути.

  • Когда дерево заполняется наполовину, вы его инвертируете: вы строите дерево, удерживающее числа, которые вы еще не использовали, затем выберите их в произвольном порядке.

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

Ответ 4

Это может помочь указать язык, на который вы ищете решение.

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

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