генератора Исчерпывающих случайных чисел

Question

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

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

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

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

Изменяется я говорю о том, могут быть диапазоны чисел или действительных чисел.

Например, если я использовал стандартный C# генератор случайных чисел для генерации 10 чисел в диапазоне [0, 9] Я получаю это:

0 0 1 2 0 1 5 6 2 6 

Как вы можете видеть, большая часть данного диапазона по-прежнему остается «неисследованный», и есть много повторений.

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

Что было бы правильным способом решить эту проблему?

Спасибо.

После комментариев: Хорошо, я согласен с тем, что случайное слово не является правильным, но я надеюсь, что вы поняли, чего я пытаюсь достичь. Я хочу изучить заданный диапазон, который может быть большим, поэтому в списке памяти не вариант. Если диапазон (0, 10), и я хочу три числа, я хочу гарантировать, что эти числа будут отличаться и что они будут «описывать диапазон» (т. Е. Они не будут в нижней половине и т. Д.).

Часть детерминизма означает, что я хотел бы использовать что-то вроде стандартного rng ​​с фиксированным семенем, поэтому я могу полностью контролировать последовательность.

Надеюсь, я сделал вещи немного яснее.

Спасибо.

Answer 1

Если вам просто нужно что-то, а как насчет этого?

maxint = 16 
step = 7 
sequence = 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9, 0 

Если вы выберете шаг вправо, он будет генерировать весь интервал перед повторением. Вы можете играть с разными значениями шага, чтобы получить что-то, что «выглядит» хорошо. Здесь «семена» вы начинаете в последовательности.

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

Фактически, вы можете сделать это лучше, составив список факторов, таких как [1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12 , 13, 14, 15, 16] - и используя перетасованные версии тех, которые вычисляют шаг * factor (mod maxint). Скажем, мы перетасовали списки примеров факторов, такие как [3, 2, 4, 5, 1], [6, 8, 9, 10, 7], [13, 16, 12, 11, 14, 15]. то мы получили бы последовательность

5, 14, 12, 3, 7, 10, 8, 15, 6, 1, 11, 0, 4, 13, 2, 9 

Размер списка факторов полностью настраиваемый, так что вы можете хранить столько памяти, сколько вам нравится. Большие списки факторов, более случайность. Нет повторов, независимо от размера списка факторов. Когда вы исчерпываете список факторов, генерировать новый так же просто, как подсчет и перетасовка.

Answer 2

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

list = [ 1 .. 100 ] 
for item,index in list: 
    location = random_integer_below(list.length - index) 
    list.switch(index,location+index) 

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

Answer 3

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

Что вам нужно сделать, это сгенерировать список чисел в нужном диапазоне, а затем использовать генератор случайных чисел для перетасовки списка. Перетасовка называется перетасовкой Фишера-Йейтса или иногда называется перетасовкой Кнута. Вот псевдокод перетасовать массив х п элементов с индексами от 0 до п -1:

для я от п -1 до 1
        J = случайного целого числа таких, что 0 ≤ J ≤ я
        подкачки х [я] и х [J]

Answer 4

Сформировать массив, содержащий диапазон, в порядке. Таким образом, массив содержит [0, 1, 2, 3, 4, 5, ... N]. Затем используйте Fisher-Yates Shuffle для скремблирования массива. Затем вы можете перебрать массив, чтобы получить ваши случайные числа.

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

Answer 5

Вот три варианта с различными компромиссами:

1. Генерировать список номеров загодя, и перемешать их с помощью fisher-yates shuffle. При необходимости выберите из списка.O (n) общей памяти и O (1) времени на элемент. Случайность так же хороша, как и PRNG, который вы использовали для тасования. Простейшая из трех альтернатив.
2. Используйте Linear Feedback Shift Register, который будет генерировать каждое значение в своей последовательности ровно один раз перед повторением. O (log n) и O (1) времени на элемент. Однако легко определить будущие значения на основе текущей стоимости, и LFSR наиболее легко сконструированы для мощности в 2 периода (но вы можете выбрать следующую большую мощность 2 и пропустить любые значения вне диапазона).
3. Использовать secure permutation based on a block cipher. Используется для любой мощности в 2 периода и с небольшим дополнительным обманом любого произвольного периода. O (log n) и O (1) времени для каждого элемента, случайность не хуже блочного шифра. Самый сложный из трех для реализации.