Visiting every cell in a grid in pseudorandom order without temporary storage

Question

Suppose you have an NxN grid, and you want to visit every cell exactly once, and in a pseudorandom order. The order doesn't have to be very random, but it does have to be seedable so that a different permutation of the grid cell ordering is possible. Is there a way to do this without simply generating a list of all cell coordinates, randomly permuting it, and indexing out of it? I mean, I want a formula (or rather, a general way of constructing such a formula) that can transform indices (i,j) into (i',j') in a one-to-one, fully-covering way.

Followup (actually intended) question: Can the same be done for an NxN grid where we only want to visit those elements for which i>j (the lower triangle)?

Answer 1

First, change the problem from a two dimensional one to a one dimensional one (any N dimensional array can be treated as a 1 dimensional array with the right algorithm for converting a one dimensional index into an N dimensional index). You want an algorithm that will visit every value between 0 and N exactly once in a seedable pseudo-random fashion with either no, or O(1) storage requirements (its unclear from your question). I personally know of no such algorithm, and doubt one exists, but then again I can't prove one doesn't exist so maybe someone cleverer than I am can provide.

EDIT

I'm wrong. You can use a Linear Feedback Shift Register. The wikipedia page shows how to set up for a maximal LSFR's from 1 to 19 bits long, and has a link to a PDF which has the setup for registers up to 168 bits long. It shouldn't be difficult to implement an algorithm which will give you 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 latter function would be to analyze N and find LFSR function for the closest bit length to it, this minimizing misses in the while loop

END EDIT

On the second part, hitting only the lower triangle just means you need to reduce N and change the way you convert the one dimensional index into a two dimensional one. 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 2

Mark cells as visited. For this you can just generate tuples at random and only visit a cell if you haven't already visited it.

For lower-triangular, you can also use a marking process to keep track of those that you've already visited, but now when you generate integers i and j, throw it away if i equals j and otherwise use the tuple (i, j) if i > j and (j, i) if j > i.

Answer 3

Since each 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 some useful answers and references.