Soft­ware Tips – Shuffling

Suppose you have a list of values which you want to arrange in a random order, such as shuffling a deck of cards. There are many possible ways to go about it, and some ways don’t perform a truly random shuffle and others take a lot of programming or a long time to execute. Here are some examples:–

1. Sort Method

   Attach a random number to each of the items to be shuffled. Then sort the random numbers into sequence with a sort program. Then take the original items in this order. This method works correctly, and could be useful if you have a random number generator, a sort program, and lots of memory to run it all in and store the random numbers. It is impractical for our purposes.

2. Obvious Replacement Shuffle

   For each item in the list, i, where there are n items (FOR I=1 to N) generate a random integer j in the range 1 to N and swop item i with item j. This method may seem to work but it is incorrect. Some orders are more likely than others. Never use this method.

3. Correct Replacement Shuffle

   Here is a correct method!
   For each item i in the list of a items, but only up to n-1 (FOR I=1 to N-1), to as follows :–

   a) Generate a random integer j in the range i to n.
   J = I + INT (RND (1) * (N-I+1})

   b) Swop value i with value j.

   This method is very fast, is easy to program, works correctly, and runs quickly. It can be easily programmed in BASIC or in machine code.