CODEWITHSUNDEEP
vb.netlistrandomshuffle
InteXX
InteXX

Reputation: 6367

Randomizing a List

I have this code, and it's working well. The input list is randomly shuffled very nicely.

But I'm having a little trouble understanding WHY it's working.

Specifically, what role does oBuffer play in all of this? Why the line at the end:

oBuffer(iRandom) = oBuffer(iIndex)

I find that when I comment it out, I end up with duplicates in the output list.

I've stepped through the code, but I'm still at a loss. What exactly is going on here?

  <Extension>
  Public Iterator Function Randomize(Of T)(Instance As IEnumerable(Of T), Rng As Random) As IEnumerable(Of T)
    Dim oBuffer As List(Of T)
    Dim iRandom As Integer
    Dim iIndex As Integer

    Instance.ThrowIfNothing(NameOf(Instance))
    Rng.ThrowIfNothing(NameOf(Rng))

    oBuffer = Instance.ToList

    For iIndex = 0 To oBuffer.Count - 1
      iRandom = Rng.Next(iIndex, oBuffer.Count)
      Yield oBuffer(iRandom)
      oBuffer(iRandom) = oBuffer(iIndex)
    Next
  End Function

Upvotes: 1

Views: 86

Answers (3)

Craig
Craig

Reputation: 2474

This is an implementation of a Fisher-Yates shuffle. There's a Wikipedia article that describes the algorithm. I believe (based on reviewing the article) that the in-place buffer is necessary in order to implement the algorithm with linear time complexity; if a separate scratch buffer were used instead, then the algorithm would be O(n²) instead of O(n).

Upvotes: 0

laancelot
laancelot

Reputation: 3207

oBuffer contains a copy of the original list, whatever this list contains.

The function iterates through the list as follows:

  1. It starts at index zero and goes all the way until it reaches the end of the list.
  2. At every loop of the For, a random number is generated which is basically an index number that's superior to the current item.
  3. It Yields the random item (returns it as the next element of the new list that it's currently building, starting from index zero).
  4. It takes the current item and puts it in the place previously occupied by the item which is already in the list that will be returned to you at the end of the function.

Now you must get why you got doubles by commenting out the last line: it's there to make sure that the current item will be randomized too. It's kinda like shoveling items in front of yourself to make sure that you don't forget one nor use one again once it's Yielded.

Upvotes: 1

dbasnett
dbasnett

Reputation: 11773

Alternative (AltRandomize). Note that this method does not require a Random instance to be passed to it.

Imports System.Runtime.CompilerServices

Module ModExtensions
    Public PRNG As New Random
    <Extension>
    Public Iterator Function AltRandomize(Of T)(Instance As IEnumerable(Of T)) As IEnumerable(Of T)
        Dim oBuffer As List(Of T)
        'uncomment following
        'Instance.ThrowIfNothing(NameOf(Instance))

        oBuffer = Instance.OrderBy(Function(n) PRNG.Next()).ToList

        For iIndex As Integer = 0 To oBuffer.Count - 1
            Yield oBuffer(iIndex)
        Next
        oBuffer.Clear()
    End Function

    <Extension>
    Public Iterator Function Randomize(Of T)(Instance As IEnumerable(Of T), Rng As Random) As IEnumerable(Of T)
        Dim oBuffer As List(Of T)
        Dim iRandom As Integer
        Dim iIndex As Integer

        'Instance.ThrowIfNothing(NameOf(Instance))
        'Rng.ThrowIfNothing(NameOf(Rng))

        oBuffer = Instance.ToList

        For iIndex = 0 To oBuffer.Count - 1
            iRandom = Rng.Next(iIndex, oBuffer.Count)
            Yield oBuffer(iRandom)
            oBuffer(iRandom) = oBuffer(iIndex)
        Next
    End Function
End Module

Upvotes: 1

Related Questions