3

I have a very large set of values (0-300000^700) and I would like to find an algorithm which would bijectively assign a unique value within the same set.

It is the equivalent of a permutation, but because of obvious memory problems, that would have to be done "on the fly". And the algorithm would need to be inverted at some point.

This problem is similar to this one in the "library of babel": http://www.fromquarkstoquasars.com/meet-the-digital-library-of-babel-a-complete-combination-of-every-possible-combination-of-letters-ever/

A LCG is used, with parameters set using the Hull-Dobell Theorem in order to assure no repetitions. The seed is used as the initial value. What I do not get is how the inverse is possible (i.e. getting the seed from the output), as I thought that would require bruteforce.

GermanoMosconi
  • 63
  • 5
  • You'll probably have more success with other SO exchanges (CS or math perhaps). Many folks here don't consider algorithms relying on deep math to be within the SO charter...as you can see by 2 votes to close. – Gene Oct 01 '15 at 03:10
  • I think some variant of this comes up repeatedly on stackoverflow. See e.g. http://stackoverflow.com/questions/32182120/to-generate-random-permutation-of-a-array-in-on-time-and-o1-space – mcdowella Oct 01 '15 at 05:02

1 Answers1

1

For LCG, seed is the same as state and serves as previous value to compute next one.LCG is known to be reversible, if

next = (a * prev + c) mod m

then

prev = (next - c) * a_inv mod m

where a_inv could be computed using Euclid's algorithm

more discussion here

Reversible pseudo-random sequence generator

Community
  • 1
  • 1
Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64