Shuffling algorithm for a "guess that tune" game

Question

I'm making a "guess that tune" game in Visual Basic 6 that is supposed to play each song in a random order:

' from frmGuessGame.frm
Private Sub Swap(ByRef Value1 As Variant, ByRef Value2 As Variant)
Dim Temporary As Variant
Temporary = Value1
Value1 = Value2
Value2 = Temporary
End Sub

Private Sub ShuffleList()
Dim LoopCtr As Integer, SwapWith As Integer
For LoopCtr = LBound(InnerPlaylist) To UBound(InnerPlaylist)
SwapWith = (Rnd * (UBound(InnerPlaylist) - LBound(InnerPlaylist))) + LBound(InnerPlaylist)
Swap InnerPlaylist(LoopCtr), InnerPlaylist(SwapWith)
Next
End Sub

My initialization function does include the Randomize statement, so it should be a good, even shuffle.

' from mdiMain.frm
Private Sub MDIForm_Load()
'initialize pseudo-random number generator
Randomize
frmMusiguess.Show
frmSplash.Show
End Sub

I'm not sure, however, that this is the best way to do it. Am I on the right track?

Answer 1

No. Your shuffle will not be random. You are stepping through each card and swapping it with another random card. This is a common bug found in many shuffling algorithms.

To illustrate why your shuffle is not random, let's assume you are shuffling three songs (1, 2, 3). There are six combinations of three song (123, 132, 213, 231, 321, 312). If your shuffle was random, each of these combinations should appear with equal probability. So if you run your shuffle algorithm 600,000 times, each combination should appear roughly 100,000 times each.

But it doesn't. When you run your shuffle algorithm 600,000 times (as written), you will see results similar to this:

To understand why your implementation produces biased results, read this article on Coding Horror: The Danger of Naïveté.

What you want is a Fisher-Yates shuffle where you swap the current card with any of the remaining cards (or itself).

Here it is in pseudo code for an in-place shuffle:

To shuffle an array a of n elements:
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

There are other types of Fisher-Yates shuffles listed here: Wikipedia: Fisher–Yates shuffle.

Answer 2

I would probably do something like this:

I don't know VB so this is pseudo code.

Private Function Shuffle(playlist) as Playlist
{
    Dim PlayList as NewPlayList
    Dim RandomIndex as Integer

    while(playlist has elements)
    {
       RandomIndex = (Random number between lowerbound and upperbound)

       remove song at RemoveIndex from playlist
       add removed song to NewPlaylist
    }

    return NewPlayList
}

The issue I have with the way you did it is that there is ample opportunity to undo the shuffle. For example, Suppose you are at index 1 and the random number is 2. You swap 1 and 2. Now suppose you are at index 2 and the random number is 1. Now you just undid the shuffle that you preformed in the previous iteration. Also, I don't like the use of the global variable InnerPlaylist.

Answer 3

For a game with no serious consequences you could just run it a bunch of times and see if it seems satisfying. For something where there are serious consequences to it not being a good enough shuffle I would think that you shouldn't wonder if a shuffle is good enough, you need to have theory that tells you it is good enough (possibly under assumptions you are happy with). Related to this Vol. 2 of The Art of Computer Programming in its first chapter gives lots of information about generating random numbers, AND how to test them.