Tomes of Delphi:
Algorithms and Data Structures

Per Larsen thought that the section on shuffling in the book could do with a little more explanation, specifically why the code in Listing 5.3 should produce more varied results than the code in Listing 5.2.

Shuffling

The book, in the section on shuffling (pages 136-138), states that the simple shuffle code in Listing 5.2 is wrong because it produces 1 permutation out of a possible n^n permutations whereas the normal way of viewing shuffling is to select one particular permutation out of the n! possible permutations, and that's done by Listing 5.3. But does that make Listing 5.2 produce any less random shufflings?

The answer is yes. Let's see how. Take a deck of 3 cards. Listing 5.2 will produce 27 possible shuffles (3^3). To see this, start with the deck ordered as ABC.

After the first time through the loop, we'll have either ABC, BAC, or CBA. In other words, A will either be swapped with itself to give ABC, swapped with B to give BAC, or swapped with C to give CBA.

After the second time through the loop we'll have 9 possible variants:

• BAC, ABC, ACB from the first loop's first possible order, ABC.
• ABC, BAC, BCA from the first loop's second possible order, BAC.
• BCA, CBA, CAB from the first loop's third possible order, CBA.

After the third and final time through the loop, we have an explosion of 27 possibilities:

• CAB, BCA, BAC from the first possibility of the second loop, BAC.
• CBA, ACB, ABC from the second possibility of the second loop, ABC.
• BCA, ABC, ACB from the third possibility of the second loop, ACB.
• CBA, ACB, ABC from the fourth possibility of the second loop, ABC.
• CAB, BCA, BAC from the fifth possibility of the second loop, BAC.
• ACB, BAC, BCA from the sixth possibility of the second loop, BCA.
• ACB, BAC, BCA from the seventh possibility of the second loop, BCA.
• ABC, CAB, CBA from the eighth possibility of the second loop, CBA.
• BAC, CBA, CAB from the ninth possibility of the second loop, CBA.

However there are only really 6 possible orderings of 3 cards: ABC, ACB, BAC, BCA, CAB, CBA. So where do the other 21 shuffles come from? Well, obviously they're just repeats of the real 6. Unfortunately, since 6 does not divide 27, it must mean that certain orderings will be produced more often than others.

From the above I get

• ABC 4 times
• ACB 5 times
• BAC 5 times
• BCA 5 times
• CAB 4 times
• CBA 4 times

In other words, if you use listing 5.2 to shuffle, you will produce certain orders more often than others and that's even before you start worrying about how biased your random-number generator is. Listing 5.3 will produce non-biased shufflings, at least as unbiased as your random-number generator is unbiased.

Another way of thinking about it is this: would you trust Listing 5.2 as a die thrower algorithm, or Listing 5.3? For an array of 3 items, they'll both produce one permutation out of six, just like a die throw. Sneakily, though, listing 5.2 produces throws biased towards three values out of the six...