A programming problem that I encounter surprisingly often is to traverse an array in roughly random order. The easiest approach is to create an auxiliary array where each cell holds an index, then shuffle the contents of the auxiliary array into random order using the Fisher-Yates algorithm. But this approach uses a lot of memory. An alternative is to programmatically generate indexes from 0 to n-1 in scrambled (but not random) order using a full cycle linear congruential generator.

To get an idea of what I mean, consider this C# code:

int n = 10; int seed = 0; FullCycle fc = new FullCycle(seed, n); for (int i = 0; i < n; ++i) { int j = fc.NextInt(); Console.WriteLine("i = " + i + " j = " + j); }

Here I’m generating indexes 0 through 9 in scrambled order. The FullCycle is a custom class as I’ll show in a moment. The 0 in the constructor is a seed value; different seeds generate the same sequence but starting at a difference number. The NextInt pulls the indexes one at a time, programmatically, without using storage.

Here is the code for the FullCycle class:

public class FullCycle { private int seed; private int n; private int prime; private int curr; public FullCycle(int seed, int n) { this.seed = seed; // don't really need to store this.n = n; this.prime = GetPrime(n); if (this.prime == -1) throw new Exception("Bad prime in FullCycle constructor"); this.curr = seed % n; // start at random location in cycle } private static int GetPrime(int n) { // first prime p where p > n/3 && p < n && // p does not divide into n evenly int p = (n / 3) + 1; while (p < n) { if (IsPrime(p) && n % p != 0) return p; ++p; } return -1; // error } private static bool IsPrime(int n) // helper for GetPrime { int divisor = 2; int maxDivisor = (int)(Math.Sqrt(n) + 1); while (divisor < maxDivisor) { if (n % divisor == 0) return false; ++divisor; } return true; } public int NextInt() // next int in the full cycle { //this.curr = (this.curr + this.prime) % this.n; // risky this.curr = ModuloOfSum(this.curr, this.prime, this.n); return this.curr; } private static int ModuloOfSum(int a, int b, int m) { // return (a + b) mod m int mod1 = a % m; int mod2 = b % m; return (mod1 + mod2) % m; } } // FullCycle

The most interesting part of this code is the helper method that finds a prime number for use by the generator. The class accepts a parameter n that represents the number of numbers. Internally, the code uses a variable called prime. For the algorithm to work properly, variable prime must be less than n, but also prime cannot divide into n evenly. Also, the sequence of generated numbers looks nicer (exactly what I mean by that is a long story) if the prime is greater than n/3. Method GetPrime finds such a prime number. Helper method IsPrime uses a crude iterative test-and-increment approach but it’s fast enough in almost all situations that I encounter. I don’t use a sieve algorithm because that requires lots of storage which defeats the purpose.

In method NextInt, if I use the basic linear congruential math form of “this.curr = (this.curr + this.prime) % this.n” I could get arithmetic overflow so I use a helper method named ModuloOfSum, which is actually an interesting little problem in itself.