Java Random sequence

Question

Let me try my best to explain my problem, well, say we have a Random class constructed with a specific seed. At this point we can use the .next() methods to get the next value derived from the seed.

I seem to need a way to get values from this sequence, but not in order. For example, if Random had a method like .get(X) which would return whatever the value would be on the Xth invocation of .next().

One way I can think of is to use a for loop X times, calling .next() on each cycle but not assigning a variable. This won't work well because of A. performance and B. it leaves the Random sequence at X, meaning if your next X is less than the original X, you'll have to reconstruct the Random.

Here's another way I thought of to solve this problem. Maybe you can derive a temporary new seed from the old seed and X, invoke next() one time and store the value, and then return the Random to its original seed. I don't know the typical way of getting this new seed out of two values, probably some crazy bitwise operations. All of my experimenting with this method has not been sufficiently random.

Well, thanks for helping!

Answer 1

You can create a cache for your Random object. What I mean is create an ArrayList that is initially empty. Then create the get(X) method that uses both the ArrayList and the Random object. When get(X) is called, you call Random's next() method X times and write the X values it generates into the ArrayList. Then return the last value.

The next time get() is called with parameter Y, you compare Y to the length of your ArrayList. If it is less than the length of the list (Y is smaller than X), then you have already computed that value earlier, and you can look it up in the ArrayList and return it. If Y is larger than the length of the list, then you grow the ArrayList by calling Random's next() method enough times to get to Y.

You'll need some memory, but it will let you go back, and the running time will be as slow as the largest X you ever see.