Псевдослучайная перестановка на лету очень большого набора без повторения и с обратной операцией
У меня очень большой набор значений (0-300000^700), и я хотел бы найти алгоритм, который бы биективно назначал уникальное значение в том же наборе.
Это эквивалент перестановки, но из-за очевидных проблем с памятью это должно быть сделано "на лету". И алгоритм должен был бы быть инвертирован в какой-то момент.
Эта проблема похожа на эту проблему в "библиотеке Вавилона": http://www.fromquarkstoquasars.com/meet-the-digital-library-of-babel-a-complete-combination-of-every-possible-combination-of-letters-ever/
Используется LCG с параметрами, установленными с использованием теоремы Халла-Добелла, чтобы гарантировать отсутствие повторений. Семя используется в качестве начального значения. Чего я не понимаю, так это того, как возможно обратное (то есть получение семян из выходных данных), так как я думал, что для этого потребуется грубая сила.
1 ответ
Для LCG начальное число совпадает с состоянием и служит предыдущим значением для вычисления следующего. Известно, что LCG является обратимым, если
next = (a * prev + c) mod m
затем
prev = (next - c) * a_inv mod m
где a_inv может быть вычислено с использованием алгоритма Евклида
больше обсуждения здесь