随机化列表

Question

我有这段代码，而且运行良好。输入列表随机打乱得很好。

但我有点难以理解它为何起作用。

具体来说，oBuffer 在这一切中扮演什么角色？为什么最后一行：

oBuffer(iRandom) = oBuffer(iIndex)

我发现当我注释掉它时，我最终在输出列表中有重复项。

代码我已经单步调试过了，但还是一头雾水。这到底是怎么回事？

  <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

Answer 1

替代（AltRandomize）。请注意，此方法不需要将 Random 实例传递给它。

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

Answer 2

oBuffer 包含原始列表的副本，无论此列表包含什么。

函数如下遍历列表：

它从索引零开始，一直到列表末尾。
在 For 的每个循环中，都会生成一个随机数，它基本上是一个优于当前项目的索引号。
它 Yields 随机项（returns 它作为当前正在构建的新列表的下一个元素，从索引零开始）。
它获取当前项目并将其放入列表中已经存在的项目先前占据的位置，该列表将在函数结束时返回给您。

现在您必须通过注释掉最后一行来了解为什么得到双打：它用于确保当前项目也将被随机化。这有点像在你面前铲东西，以确保你不会忘记一个，也不会在 Yielded 后再次使用它。

Answer 3

这是 Fisher-Yates 洗牌的实现。有一个描述算法的 Wikipedia article。我相信（基于对文章的回顾）就地缓冲区对于实现具有线性时间复杂度的算法是必要的；如果使用单独的暂存缓冲区，则算法将是 O(n²) 而不是 O(n)。

随机化列表

Randomizing a List

vb.net

random

shuffle

list