Рандомизация списка

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

oBuffer содержит копию исходного списка, независимо от того, что этот список содержит.

Функция выполняет итерацию по списку следующим образом:

1. Она начинается с нуля индекса и продолжается вплоть до конца списка.
2. При каждом l oop из For генерируется случайное число, которое в основном является индексным числом, которое превосходит текущий элемент.
3. Это Yields случайный элемент (возвращает его как следующий элемент нового списка, который он в данный момент создает, начиная с нуля индекса).
4. Он берет текущий элемент и помещает его на место ранее занятый элементом, который уже находится в списке и будет возвращен вам в конце функции.

Теперь вы должны понять, почему вы получили двойные значения, закомментировав последнюю строку: она есть чтобы убедиться, что текущий элемент тоже будет рандомизирован. Это все равно, что переложить вещи перед собой, чтобы убедиться, что вы их не забыли и не используете снова, когда оно Yield изд.

Answer 2

Альтернатива (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 3

Это реализация шаффла Фишера-Йейтса. В статье Википедии описывается алгоритм. Я полагаю (основываясь на обзоре статьи), что буфер на месте необходим для реализации алгоритма с линейной временной сложностью; если вместо этого будет использоваться отдельный рабочий буфер, то алгоритм будет O (n²) вместо O (n).