c# - 如何在 C# 中解决 Randomize in place 算法？

Question

我正在阅读算法简介 - 第三版，现在，我必须实现 RANDOMIZE-IN-PLACE 算法，该算法必须置换当前数组中的每个值。 本书提供的伪代码如下所示:

n = A.length
for i = 1 to n
swap A[i] with A[Random(i, n)]

我尝试在 C# 上实现它，但有时会收到 IndexOutOfRangeException(仅在某些情况下)。我曾经调试过算法，发现当

randomValue = array[randomNumber.Next(index, upperBound)];

index 等于 array.Length - 1 而 upperBound 是 array.Length - 1 (换句话说，index 和 upperBound 是相同的值，并且 .Next看起来像这样 .Next(9, 9) 例如)，随机生成器能够生成数字 10(下限/上限 + 1)，这正是我的 array.Length。如果有人知道如何解决这对我很有帮助。再次感谢。这是我的 C# 代码。

namespace RandomizedAlgorithms
{

using System;

class RandomizeInPlace
{
    static void Main()
    {
        int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        Randomize(array);

        for (int index = 0; index <= array.Length - 1 ; index++)
        {
            Console.WriteLine(array[index]);
        }
    }

    private static void Randomize(int[] array)
    {
        Random randomNumber = new Random();
        int swapVariable = 0;
        int randomValue = 0;
        int upperBound = array.Length - 1;

        for (int index = 0; index <= array.Length - 1 ; index++)
        {
            randomValue = array[randomNumber.Next(index, upperBound)];
            swapVariable = array[randomValue];
            array[randomValue] = array[index];
            array[index] = swapVariable;
        }
    }
}

Answer 1

您需要存储要交换的元素的随机索引，而不是数组值本身:

private static void Randomize(int[] array)
{
    Random randomNumber = new Random();
    int swapVariable = 0;
    int randomIndex;                // <-- renamed this
    int upperBound = array.Length;  // <-- See the comments

    for(int index = 0; index < array.Length; index++)
    {
        // Note: besides the minor changes above, the real fix is removing array[...]
        randomIndex = randomNumber.Next(index + 1, upperBound);
        swapVariable = array[randomIndex];
        array[randomIndex] = array[index];
        array[index] = swapVariable;
    }
}

我已尽可能少地更改您的代码，还可以进行其他改进。请注意，此版本允许元素与其自身“交换”，这可能是也可能不是您想要的。