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

Question

Предположим, у меня есть последовательность чисел: {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

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

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

---

Edit:

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

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

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

Answer 1

Существует простая функция, которая генерирует перестановку [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, без гарантий его статистических свойств.

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

Я отдыхаю.

Answer 5

Ваш ввод описывается как 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 отличных значений при взятии мод m+1, если вы не хотите кодировать свой собственный генератор.

Answer 6

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

Answer 7

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

Answer 8

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

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

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

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

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

result = rand() % 8 + 10

Получит целое число от 10 до 17.

Answer 9

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

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

Answer 10

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

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