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

Этот вопрос аналогичен перетасовке колоды (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, Если вы не хотите кодировать твой собственный генератор.