# Shuffling algorithm for a “guess that tune” game

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
'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?

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:

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.

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