Shuffling through all the points in a 3-dimensional space without storing all possible coordinates

Question

I'm programming a 3-dimensional cellular automata. The way I'm iterating through it right now in each generation is:

1. Create a list of all possible coordinates in the 3D space.
2. Shuffle the list.
3. Iterate through the list until all coordinates have been visited.
4. Goto 2.

Here's the code:

I've a simple 3 integer struct

public class Coordinate
{
    public int x;
    public int y;
    public int z;

    public Coordinate(int x, int y, int z) {this.x = x; this.y = y; this.z = z;}
}

then at some point I do this:

List<Coordinate> all_coordinates = new ArrayList<>();
[...]
for(int z=0 ; z<length ; z++)
{
    for(int x=0 ; x<diameter ; x++)
    {
        for(int y=0 ; y<diameter ; y++)
        {
            all_coordinates.add(new Coordinate(x,y,z));
        }
    }
}

and then in the main algorithm I do this:

private void next_generation() 
{ 
    Collections.shuffle(all_coordinates);
    for (int i=0 ; i < all_coordinates.size() ; i++) 
    {
        [...]
    }
}

The problem is, once the automata gets too large, the list containing all possible points gets huge. I need a way to shuffle through all the points without having to actually store all the possible points in memory. How should I go about this?

Answer 1

One way to do this is to start by mapping your three dimensional coordinates into a single dimension. Let's say that your three dimensions' sizes are X, Y, and Z. So your x coordinate goes from 0 to X-1, etc. The full size of your space is X*Y*Z. We'll call that S.

To map any coordinate in 3-space to 1-space, you use the formula (x*X) + (Y*y) + z.

Of course, once you generate the numbers, you have to convert back to 3-space. That's a simple matter of reversing the conversion above. Assuming that coord is the 1-space coordinate:

x = coord/X
coord = coord % X
y = coord/Y
z = coord % Y

Now, with a single dimension to work with, you've simplified the problem to one of generating all the numbers from 0 to S in pseudo-random order, without duplication.

I know of at least three ways to do this. The simplest uses a multiplicative inverse, as I showed here: Given a number, produce another random number that is the same every time and distinct from all other results.

When you've generated all of the numbers, you "re-shuffle" the list by picking a different x and m values for the multiplicative inverse calculations.

Another way of creating a non-repeating pseudo-random sequence in a particular range is with a linear feedback shift register. I don't have a ready example, but I have used them. To change the order, (i.e. re-shuffle), you re-initialize the generator with different parameters.

You might also be interested in the answers to this question: Unique (non-repeating) random numbers in O(1)?. That user was only looking for 1,000 numbers, so he could use a table, and the accepted answer reflects that. Other answers cover the LFSR, and a Linear congruential generator that is designed with a specific period.

None of the methods I mentioned require that you maintain much state. The amount of state you need to maintain is constant, whether your range is 20 or 20,000,000.

Note that all of the methods I mentioned above give pseudo-random sequences. They will not be truly random, but they'll likely be close enough to random to fit your needs.