Is there an easy way to randomize a list in VB.NET?

Question

I have a list of type System.IO.FileInfo, and I would like to randomize the list. I thought I remember seeing something like list.randomize() a little while back but I cannot find where I may have seen that.

My first foray into this yielded me with this function:

Private Shared Sub GetRandom(ByVal oMax As Integer, ByRef currentVals As List(Of Integer))
    Dim oRand As New Random(Now.Millisecond)
    Dim oTemp As Integer = -1
    Do Until currentVals.Count = IMG_COUNT
        oTemp = oRand.Next(1, oMax)
        If Not currentVals.Contains(oTemp) Then currentVals.Add(oTemp)
    Loop
End Sub

I send it the max val I want it to iterate up to, and a reference to the list I want the randomized content in. The variable IMG_COUNT is set farther up in the script, designating how many random images I want displayed.

Thanks guys, I appreciate it :D

Answer 1

Check out the Fisher-Yates shuffle algorithm here: http://en.wikipedia.org/wiki/Knuth_shuffle

with a more concise discussion by this site's chief overlord here: http://www.codinghorror.com/blog/archives/001015.html

There is a simple C# implementation in the blog entry that should be real easy to change to VB.NET

Answer 2

I've extended the List class with the following Randomize() function to use the Fisher-Yates shuffle algorithm:

''' <summary>
''' Randomizes the contents of the list using Fisher–Yates shuffle (a.k.a. Knuth shuffle).
''' </summary>
''' <typeparam name="T"></typeparam>
''' <param name="list"></param>
''' <returns>Randomized result</returns>
''' <remarks></remarks>
<Extension()>
Function Randomize(Of T)(ByVal list As List(Of T)) As List(Of T)
    Dim rand As New Random()
    Dim temp As T
    Dim indexRand As Integer
    Dim indexLast As Integer = list.Count - 1
    For index As Integer = 0 To indexLast
        indexRand = rand.Next(index, indexLast)
        temp = list(indexRand)
        list(indexRand) = list(index)
        list(index) = temp
    Next index
    Return list
End Function

Answer 3

Build a Comparer:

Public Class Randomizer(Of T)
    Implements IComparer(Of T)

    ''// Ensures different instances are sorted in different orders
    Private Shared Salter As New Random() ''// only as random as your seed
    Private Salt As Integer
    Public Sub New()
        Salt = Salter.Next(Integer.MinValue, Integer.MaxValue)
    End Sub

    Private Shared sha As New SHA1CryptoServiceProvider()
    Private Function HashNSalt(ByVal x As Integer) As Integer
      Dim b() As Byte = sha.ComputeHash(BitConverter.GetBytes(x))
      Dim r As Integer = 0
      For i As Integer = 0 To b.Length - 1 Step 4
          r = r Xor BitConverter.ToInt32(b, i)
      Next

      Return r Xor Salt
    End Function

    Public Function Compare(x As T, y As T) As Integer _
        Implements IComparer(Of T).Compare

        Return HashNSalt(x.GetHashCode()).CompareTo(HashNSalt(y.GetHashCode()))
    End Function
End Class

Use it like this, assuming you mean a generic List(Of FileInfo):

list.Sort(New Randomizer(Of IO.FileInfo)())

You can also use a closure to make the random value 'sticky' and then just use linq's .OrderBy() on that (C# this time, because the VB lambda syntax is ugly):

list = list.OrderBy(a => Guid.NewGuid()).ToList();

Explained here, along with why it might not even be as fast as real shuffle:
http://www.codinghorror.com/blog/archives/001008.html?r=31644

Answer 4

There are several reasonable methods of shuffling.

One has already been mentioned. (The Knuth Shuffle.)

Another method would be to assign a "weight" to each element and sort the list according to that "weight." This method is possible but would be unweildy because you cannot inherit from FileInfo.

One final method would be to randomly select an element in the original list and add it to a new list. Of course, that is, if you don't mind creating a new list. (Haven't tested this code...)

        Dim rnd As New Random
        Dim lstOriginal As New List(Of FileInfo)
        Dim lstNew As New List(Of FileInfo)

        While lstOriginal.Count > 0
            Dim idx As Integer = rnd.Next(0, lstOriginal.Count - 1)
            lstNew.Add(lstOriginal(idx))
            lstOriginal.RemoveAt(idx)
        End While

Answer 5

You could also implement a shuffle, many ways to do this, the simplest is randomly pick a item and insert it into a new location a bunch of times.

Answer 6

If you have the number of elements then a pseudo-random method can be used whereby you choose the first element at random (e.g. using the inbuilt random number function) then add a prime and take the remainder after division by the number of values. e.g. for a list of 10 you could do i = (i + prime) % 10 to generated indices i from some starting value. As long as the prime is greater than the number of values in the list then you create a sequence which runs through all of the numbers 0...n where n is the number of values - 1, but in a pseudorandom order.

Answer 7

Dim oRand As New Random() 'do not seed!!!!
Private Sub GetRandom(ByRef currentVals As List(Of Integer))
    Dim i As New List(Of Integer), j As Integer
    For x As Integer = 0 To currentVals.Count - 1
        j = oRand.Next(0, currentVals.Count)
        i.Add(currentVals(j))
        currentVals.RemoveAt(j)
    Next
    currentVals = i
End Sub

Answer 8

You could create custom comparer that just returns a random number, then sort the list using this comparer. It could be horribly inefficient and cause an almost infinite loop, but might be worth a try.