Prior Page Next Page This Chapter Prior Chapter

Random Permutations

It is handy to create a random reordering of some items. For example doing a complete randomization of a deck of cards. This requires creating a random permutation of the cards. There are two common ways to permute a finite set of items.

The first is easy. Assign a random key to each item of the set. Sort the items by the random key. This requires having a good random number generator and a sort algorithm.

In doing this one should do a little worrying about duplicate keys; however if the random number is sufficiently greater than the size of the set there should not be a problem.

The second method is faster, cleaner, and doesn't require a sort routine. Line up the items you want to permute in an array. Then take the last element and swap it with any of the items (including itself). Now consider the array as one shorter and do it again. Each swap will result in the last element randomly positioned.

TYPE datat = 0..M; TYPE indxt = 0..N-1; TYPE rowt = ARRAY [indxt] of datat; PROCEDURE Permute( VAR data: rowt; n: indxt ) { data is the array to be permuted; n is how many elements of the array to permute. tauset needs to called before this routine is used. }

VAR
i, j : indxt;
x    : datat;
BEGIN

    FOR i := n-1 DOWNTO 1 DO
    BEGIN
        j       := taurand( i );
        x       := data[i];
        data[i] := data[j];
        data[j] := x;
    END
END;

This algorithm is handy, and a bit too general for Pascal; you will need to modify the types for each particular usage. We will use it later as if the types matched properly.

Other Random Distributions

So far we have only considered random sequences in which the distribution of the number has been uniform. Sometimes it is useful to have other distributions. For example a Gaussian or normal distribution is handy for simulating errors.

If one sums 12 uniform randoms in the range -1.0 to +1.0 the result is a Gaussian number with a mean of zero and a standard deviation of one.

You should try to think of other transformations to uniform random distributions that give other random distributions. One day next year they will come in handy.

How about discrete finite distributions with some probability of yielding each discrete value. Could you write a random program that took as input an array of probabilities, it should output an index acording to the probabilities given. using only a good uniform pseudo-random generator and a simple algorithm?