Ищете алгоритм для выдачи последовательности чисел в (псевдо) случайном порядке

StackOverflow https://stackoverflow.com/questions/732700

Вопрос

Предположим, у меня есть последовательность чисел:{n, n+1, n+2, ...n + m}

Не сохраняя числа заранее, я хочу создать функцию f(), которая, учитывая последовательность {1,2,3,...m}, выдаст исходный набор в случайном (или, по крайней мере, псевдослучайном) порядке.

Например, предположим, что моя последовательность такова {10, 11, 12, 13, 14, 15, 16, 17}

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

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

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

Редактировать:

Чтобы прояснить немного больше, я не хочу сохранять исходную последовательность или перетасованную последовательность.Я хочу сгенерировать функцию f() из исходной последовательности.

Что расстраивает, так это то, что я видел это, я просто не могу вспомнить достаточно об этом, чтобы найти его снова с помощью Google.

Алгоритм Фишера-Йейтса отлично подходит для перестановки или перетасовки колоды, но это не то, что я ищу.

Это было полезно?

Решение

Существует простая функция , которая генерирует перестановку [0..m-1] для данного m.Просто выберите номер k, относительно простой по отношению к m и пусть f(i)=(k*i) mod m.Это всегда генерирует перестановку (никаких повторений на 0<=i<m).Это работает лучше, если k больше , чем m.

Например, m = 20, пусть k= 137 (код на Python, % означает по модулю):

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

Это очень простой PRNG, никаких гарантий относительно его статистических свойств.

Другие советы

Этот вопрос аналогичен перетасовке колоды из (m + 1) карт, пронумерованных [n, ..., n + m].Обратите внимание , что нумерация (и, следовательно , n) не имеет значения;важно то, что мы можем отличить карты друг от друга.(Вы можете просто добавить n вернемся позже, если пожелаете.)

Чтобы сделать то, что вы хотите, вы можете выполнить Фишер-Йейтс перетасовывает и просто следите за тем, какие индексы были выбраны за то, что до сих пор тасовал.Это позволит вам избежать хранения другой копии самих значений, как и было запрошено.

Ваш вопрос немного сбивает с толку, поскольку звучит так, как будто вы хотите вернуть всю исходную последовательность обратно, но тогда у вас есть и 4, и 8, сопоставляющиеся с 10, и ничего, сопоставляющегося с 12.

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

Также обратите внимание, что n не имеет значения.Вы всегда можете использовать 0,1,2,...m, а затем добавить n ко всему, если это необходимо.

Предполагая, что я правильно интерпретировал это, и вы на самом деле ищете алгоритм перемешивания (т. е.случайная перестановка, называемая перетасовкой по аналогии с перетасовыванием колоды карт), взгляните на Фишер-Йейтс

[Редактировать] Хорошо, основываясь на вашем обновлении, проблема, с которой вы сталкиваетесь, заключается в следующем:Вы не хотите кодировать перестановку явно, но вы должны как-то ее закодировать, чтобы сконструировать f .Самый простой способ - просто сохранить переставленные индексы в массиве, но если вы по какой-то причине не хотите этого делать (напримерслишком большой), вы можете закодировать его различными способами.Однако бесплатного обеда не бывает, поскольку существуют теоретико-информационные ограничения на то, насколько простым это может быть.В любом случае, вы можете почерпнуть некоторые идеи, просмотрев работу над "перестановками кодирования", например, что-то вроде этот документ

Вот некоторый псевдокод на моем собственном выдуманном языке:

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray

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

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

Если вам нужно отображение 1: 1, используйте Фишера-Йейтса, как упоминалось в других ответах.

Если вас не волнует сопоставление 1: 1, и вам просто нужно, чтобы все результирующие значения были из заданной последовательности (с возможностью повторов), то вы можете использовать случайную функцию с указанным диапазоном.

Например, в C ++ вы могли бы использовать rand() следующим образом -

result = rand() % (m+1) + n

Итак, для вашего примера, 

result = rand() % 8 + 10

Это привело бы к получению целого числа от 10 до 17.

Ты можешь подгоните многочлен к выбранной последовательности;Я бы предположил, что это то, что показал вам ваш коллега.Однако это не сэкономит место по сравнению с простым запоминанием перестановки.

Вы можете сгенерировать перестановку первых n целых чисел, используя блочный шифр и сворачивание xor, согласно мой предыдущий ответ.

Невозможно вернуть значения, не сохранив где-нибудь результаты исходной функции.Рассуждения:

Ваш генератор случайных чисел подсказывает вам вернуть эти значения из исходной последовательности:5-й, 11-й, 3-й.

Итак, вы пропускаете первые четыре значения, возвращаете 5- е, пропускаете еще 5, возвращаете 11 - е...теперь, как вы возвращаете 3-й, не сохраняя его где-нибудь?

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

Я оставляю свое дело в покое.

Ваш вклад описывается следующим образом f(x) => x + 9, или в более общем плане f(x) => n - 1 + x как x начинается с 1.

Вы ссылаетесь на еще один вопрос который описывает функцию r(x) который сопоставляет x с перетасованным значением, 0 <= r(x) <= m.

итак f(r(x) + 1) или (r(x) + n)должно дать вам ту ценность, которую вы хотите.

Для небольших m, вы также должны быть в состоянии найти начальные значения стандартного генератора случайных чисел по следу и ошибке, которые затем генерируют m+1 различные значения при использовании mod m+1 если вы не хотите кодировать свой собственный генератор.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top