Recipe 5.32. Shuffling a String

Problem

You want to shuffle the order of the characters in a string quickly but thoroughly.

Solution

Sample code folder: Chapter 05\StringShuffle

The best technique is to loop through each character location once, swapping the character at that location with a character at a random location anywhere in the string.

Discussion

The basic algorithm for shuffling a string, as presented here, is also good for shuffling arrays or any other ordered data. This algorithm takes a finite amount of time to run, and the results are as random as the random number generator used.

A walk through the code explains the process clearly. These lines declare the variables required and initialize the random number generator to a unique sequence, using the system clock for the random number generator's seed:

 Dim counter As Integer Dim position As Integer Dim holdChar As Char Dim jumbleMethod As New Random Dim quote As String = "The important thing is not to " & _    "stop questioning. --Albert Einstein" 

To manipulate the individual characters of the string, it's best to convert the string to a character array:

 Dim chars() As Char = CType(quote, Char()) 

This allows for swapping the characters in memory without having to make multiple copies of immutable strings. You can directly access a string's individual characters using the string's Chars property, but this property is read-only. In this case, we need to store new characters into the string's locations during each swap.

The following loop is the core of the shuffling algorithm:

 For counter = 0 To chars.Length - 1    position = jumbleMethod.Next Mod chars.Length    holdChar = chars(counter)    chars(counter) = chars(position)    chars(position) = holdChar Next counter 

Each character is sequentially processed by swapping it with another character located randomly at any position in the string. This means that a character might even get swapped with itself occasionally, but that does not reduce the randomness of the results. This loop guarantees that each character gets swapped at least once, but statistically speaking each character gets swapped twice, on average.

The last two lines convert the character array back to a string and then display the result in a message box, as shown in Figure 5-36:

 Dim result As String = New String(chars) MsgBox(result) 

Figure 5-36. The shuffled string

The sample string will be shuffled into a unique random order every time the sample code is run.

See Also

Recipes 6.27 and 8.5 show additional uses of random numbers.