Psuedo-Random Traversal of a Set

Question

I've been reading Game Coding Complete (4th Edition) and I'm having a few problems understanding the "Pseudo-Random Traversal of a Set" path in the "Grab Bag of Useful Stuff" section in Chapter 3.

Have you ever wondered how the “random” button on your CD player works? It will play every song on your CD randomly without playing the same song twice. That's a really useful solution for making sure players in your games see the widest variety of features like objects, effects, or characters before they have the chance of seeing the same ones over again.

After this description, it goes on to talk about an implementation in C++ that I've tried to implement in Java, but have been unable to replicate successfully. It also briefly describes how it works, but I don't get it either.

I found this StackOverflow answer to a similar question, but unfortunately the link to examples in the answer is dead and I don't understand the Wikipedia article either, although the description about what it does seems to describe what I'm looking for.

To be clear, I'm not looking for a way to randomly re-order a collection. I am looking for a way to randomly select an element from a collection exactly once before repeating.

Can someone explain how this behavior works and provide an example in Java? Thanks!

[EDIT] I figured it might be useful to have an excerpt of the implementation in here to help explain what I'm talking about.

Here's how it works. A skip value is calculated by choosing three random values greater than zero. These values become the coefficients of the quadratic, and the domain value (x) is set to the ordinal value of the set:

Skip = RandomA * (members * members) + (RandomB * members) + RandomC

Armed with this skip value, you can use this piece of code to traverse the entire set exactly once, in a pseudo-random order:

nextMember += skip;
nextMember %= prime;

The value of skip is so much larger than the number of members of your set that the chosen value seems to skip around at random. Of course, this code is inside a while loop to catch the case where the value chosen is larger than your set but still smaller than the prime number.

Answer 1

Here's an example of what this looks like in the case of getting a random permutation of a set of characters:

public static void main(String[] args) {
    // Setup
    char[] chars = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
    int prime = 11; // MUST be greater than the length of the set
    int skip = 0;
    int nextMember = 0;

    // If the skip value is divisible by the prime number, we will only access
    // index 0, and this is not what we want.
    while (skip % prime == 0) {
        // Generate three random positive, non-zero numbers
        int ra = new Random().nextInt(prime) + 1;
        int rb = new Random().nextInt(prime) + 1;
        int rc = new Random().nextInt(prime) + 1;
        skip = ra * chars.length * chars.length + rb * chars.length + rc;
    }

    String result = "";
    for (int x = 0; x < chars.length; x++) {
        do {
            nextMember += skip;
            nextMember %= prime;
        } while (nextMember <= 0 || nextMember > chars.length);
        result += chars[nextMember - 1];
    }

    // Print result
    System.out.println(result);
}

Most of the conditions of the example from the book are present in the code example above, but with a few exceptions. First of all, if the skip is divisible by the prime number, than this algorithm doesn't work as it will only access index 0 due to this part of the code:

            nextMember += skip;
            nextMember %= prime;

Secondly, the three coefficients are in between the range of 1 and the prime number, inclusive, but this does not have to be the case. It can be any positive, non-zero number, but I find that if I do that I'll have integer overflow and get a negative skip value, which doesn't work. This particular case can be fixed by taking the absolute value of the skip value.

Lastly, you need to check if the next member a number between 1 and the length of the set, inclusive, and then get the member at the index one less than that. If you don't do this (if you only check to see if the number is less than the length of the set), then you'll end up with the first element in the array at the end of each permutation whenever you run the program, which is interesting but undesirable for a random traversal.

The program will select a different index until all indexes are visited, and then it will repeat. When it repeats, the same permutation will be produced (which is how it's supposed to work), so if we wanted a different permutation, you would need to calculate a new skip value. The program works due to the properties of quadratic equations and primes. I can't explain it in detail without being doubtful of what I'm saying, and a more or less similar description is already present in the book.

I've run a slightly modified version of this program a couple of times on sets of 3 and 5 characters. For both, each permutation appears evenly, with an average absolute difference of 0.0413% and 0.000000466726%, respectively, from the average number of times expected for an even distribution. Both were run to produce 60 million samples. No permutations where characters are repeated are produced.

Answer 2

The algorithm is actually very far from random or random-looking.

This method is simply stepping with a period of skip % prime, then removing all values that lie outside of array.length.

With a small prime you can easily make out the patterns:

Fill the array with [0, 1, 2, 3..., 9] you and select coefficients 3, 5, 7 - prime 11, we get a skip of 753. However, 753 % 11 is 5, so the actual step is 5.

The result (using your implementation) is

[4, 9, 3, 8, 2, 7, 1, 6, 0, 5]

We can see the steps here:

+5, -6, +5, -6, +5, -6, +5, -6, +5

(the -6 comes from (x + 5) % 11, which for 6 <= x <= 10 is the same as x - 6)

You'll see this pattern no matter what number you choose.

Answer 3

Randomly selecting non-repeating elements from a collection is the same as shuffling it and selecting in order from the shuffled list.

shuffled = shuffle(my_list);
first = pop(shuffled);
second = pop(shuffled);

Answer 4

I would just create a copy of the list by inserting the members of the original list at random positions, something like this:

List<T> randomOrder = new ArrayList<T>(original.size());
Random rand = new Random();
int currentSize = 0;
for (T member : original) {
    randomOrder.add(rand.nextInt(++currentSize), member);
}

So randomOrder should become a copy of the original list but with a different, random order. The original list will not be affected. (Replace T with the type of your list, obviously.)

Answer 5

Here's an example:

import java.util.*;

public class Randy {

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        ArrayList<String> copy = new ArrayList<String>();
        list.add("Jack");
        list.add("Tess");
        list.add("Alex");
        list.add("Jeff");
        list.add("Kelli");
        Random randy = new Random();
        int size = list.size();
        for(int i = 0; i < size; i++) {
            int r = randy.nextInt(list.size());
            System.out.println(list.get(r));
            copy.add(list.get(r));
            list.remove(r);
        }
        list = copy;
        copy.clear();
    }

}

Here, I have an ArrayList list comprised of String Objects. Then in the for loop, I print out those Strings in a random order and remove the randomly selected element from list so there are no repeated outputs. But before I remove the element, I add it to the other ArrayList, copy, so I do not lose the elements altogether. At the very end I set list equal to copy and everything is restored and you can repeat this process over and over again.