Visit each grid cell in a pseudo-random order without temporary storage

Question

Suppose you have an NxN grid and you want to visit each cell exactly once and in a pseudo-random order. The order does not have to be very random, but it has to be seeded, so that another permutation of the ordering of the grid cell is possible. Is there a way to do this by simply not creating a list of all cell coordinates, randomly rearranging it and indexing from it? I mean, I need a formula (or rather, a general way of constructing such a formula) that can convert the indices (i,j) into (i',j') one-to-one, fully encompassing way.

The next (actually asked) question: can this be done for the NxN grid, where we only want to visit those elements for which i>j (the lower triangle)?

Answer 1

Since every number N in the range 0..ROWS * COLS-1 deterministically points to a cell (N DIV ROWS, N MOD ROWS), this question is equivalent to this SO question . It has helpful answers and links.

Answer 2

First, change the problem from two-dimensional to one-dimensional (any N-dimensional array can be considered as a one-dimensional array with the correct algorithm for converting a one-dimensional index to an N-dimensional index). You need an algorithm that will visit each value from 0 to N exactly once in a pseudo-random seeded order with storage requirements no or O (1) (it is not clear from your question). I personally do not know such an algorithm, and I doubt that it exists, but then I can not prove that this does not exist, maybe someone is smarter than I can provide.

EDIT

I am wrong. You can use the Linear Feedback Shift Register . The wikipedia page shows how to configure the maximum LSFR with a length of 1 to 19 bits, and has a link to the PDF, which has a setting for registers up to 168 bits in length. It is easy to implement an algorithm that will give you a pseudo-random value from 1 to any N

 // a 31 bit LFSR // based on http://forums.sun.com/thread.jspa?threadID=5276320 public static int getNextValue(int register) { int t31 = (register & (1 << 30)) >>> 30; int t28 = (register & (1 << 27)) >>> 27; int input = t31 ^ t28; register <<= 1; register |= input; register &= 0x7fffffff; // mask with this to ensure 0s in the high order bits return register; } public static int getNextValueBelowN(int value, int n) { do { value = getNextValue(value); } while (value > n); return value; } 

An obvious optimization for the last function is to analyze N and search for the LFSR function for the closest bit length to it, this is to minimize misses in the while loop

End edit

In the second part, hitting only the lower triangle means that you need to reduce N and change the way you convert the one-dimensional index to two-dimensional. For instance:

 public static int getMaxValue(int dimension) { int retVal = 0; while (dimension > 0) { retVal += dimension--; } return retVal; } public static int getMaxValueFast(int dimension) { int retVal = 0; if (dimension % 1 == 1) { retVal += dimension--; } retVal += ((dimension + 1) * dimension / 2); return retVal; } public static Point getCoordinates(int index, int dimension) { Point retVal = new Point(); while (index >= dimension) { ++retVal.x; index -= dimension--; } retVal.y = index; return retVal; } 

Answer 3

Mark cells as visited. To do this, you can simply generate tuples in a random order and only visit the cell if you have not visited it yet.

For lower triangles, you can also use the marking process to track the ones you have already visited, but now that you are generating integers i and j , throw it away if i is equal to j and otherwise use the tuple (i, j) if i > j and (j, i) if j > i .