C#中的随机数生成器 - 独特值

Question

我正忙于使用C#编写一个数组。我可以使用随机生成器填充它，但现在我的问题是如何检查该值是否已经在数组中，如果是，则生成一个新值。

额外信息：
最大值：100
元素数量：100

重要提示，请继续完善我的想法

我的想法：

public void FillArray(int[] A, int Range)
{
    for (int I = 0; I < A.Length; I++)
    {
        A[I] = ValidNumber(T, I, Range);
    }
} /* Fill Array */

选择排序的实现

public void SelectionSort(int[] A)
{
    int K, X;
    for (int I = 0; I < A.Length - 1; I++)
    {
        K = I;
        X = A[K];
        for (int J = I + 1; J < A.Length; J++)
        {
            if (A[J] < X)
            {
                K = J;
                X = A[K];
            }
        }
        A[K] = A[I];
        A[I] = X;
    }
} /* Selection sort */

这只是一些想法，现在我想知道如何修复它，以便我可以使用选择排序查看是否已经存在（fillarray）相同的值，如果有，则用新的随机值替换它。因此，我想创建一个随机数组，其中包含1到100之间的整数，顺序随机。

- ShallowHeart

---

这似乎是一份作业，特别是在下面有注释的（有效、好的）建议和看起来是作业一部分的框架代码：“从这段代码开始”。 - Benjamin Podszun

是的，这确实是作业的一部分，我不会撒谎，我只是卡在一个地方，想要一些提示/反馈，这并不是坏事，我想。 - ShallowHeart

适当的代码缩进和更好的变量命名将有助于人们理解你的代码，从而为你提供更好的解决方案。 - CesarGon

Answer 1

如何做到这一点，同时还能检查值是否已经存在于数组中，如果是，则生成一个新值。

永远不要那样做，因为那是一个非常糟糕的主意。举个例子说明为什么这是一个可怕的想法，考虑另一个版本的同样问题：按以下过程将一百万个数字随机排序：

1. 从一到一百万中选择一个数字。 2. 检查它是否已经在列表中。 3. 如果是，则返回步骤1. 4. 否则，将数字添加到列表中。 5. 列表上是否有一百万个项目？如果是，则完成。如果不是，则返回步骤1。

显然，这个过程是有效的。但这是一个好主意吗？ 假设你快要完成了，列表上有999999个项目，唯一缺少的项目是857313。你该怎么办呢？ 你选择一个随机数，比如12。现在，你检查列表中的999999个项目，看看其中有没有12。12可能是你选择的第一个数字之一，因此找到它可能会很快。或者它可能是最后一个数字之一，这将需要很长时间。平均需要500000次检查才能确定12是否在列表中。而事实上，12就在列表中，因为列表中只缺少一个数字。

12不行，返回开始。再选择另一个随机数，比如53259。它在列表中吗？又是另外的500000次检查。

一直这样做，直到生成857313，这会发生在每一百万次尝试中的一次。

因此，平均来说，将最后一个项目放入列表中需要500000 x 1000000 = 五百亿次比较。可能需要更多。可能需要数万亿次比较。或者你可能很幸运，只需要一次。但平均来说，需要半万亿次比较。

这是一种产生列表的随机排序的可怕方法。

有两种很好的方法可以对列表进行随机排序.

(1) 制作一个设备，该设备可以根据排序函数对列表进行排序。提供基于随机种子的稳定排序.

请注意，您不应通过创建一个在被问及“A是否比B大？”时返回随机结果的方法来生成随机顺序。 这是一种不稳定的排序; 许多排序算法都基于稳定排序，当给定不稳定的排序时，它们将进入无限循环或出现其他错误行为。

该算法的时间复杂度为O(n lg n)，并且具有一个不错的特点，即它非常易于使用标准部件编写，正如其他答案所示。 在典型实现中，对于小列表，它也非常快速。

(2) 从源列表中按索引随机选择一项，删除它，并将其放在目标列表上。

后者称为Knuth Shuffle或Fischer-Yates Shuffle，是一种非常快速的算法。 您可以通过“就地”将现有数组变异为洗牌顺序，也可以通过创建新列表来完成。 它还具有一个不错的特性，即您可以“付费玩”，按需要随机洗牌列表的“顶部”。 如果您有一百万个项目需要洗牌，但您只需要前一百个，请只为前一百个计算排序顺序并调用即可。

- Eric Lippert

---

我觉得第二条建议非常出色。 - Shakti Prakash Singh

很棒的答案，这是一个很好的方法，因为这个问题涉及到作业，你不仅仅是说复制这个就完成了 +1 - Max Rasguido

我目前正在使用第二种方法，它非常棒。很好的答案，+1。 - Abluescarab

Answer 2

以下代码将会生成一个包含1-100数字的随机顺序数组。

    Random rnd = new Random();
    var randomNumbers = Enumerable.Range(1, 100).OrderBy(i => rnd.Next()).ToArray();

- Jesper Palm

---

Random类的默认空构造函数会使用Enviroment.TickCount作为种子。 - Jesper Palm

不，你不应该这样做。只有当你希望稍后能够提供相同的种子时，才应该提供一个种子。否则，依赖默认的种子即可。 - P Daddy

请注意，DateTime.Now.Millisecond 只有 1000 个唯一值。这是一个非常小的种子范围。 - P Daddy

@Jesper：这个实现不稳定，可能永远无法完成，因为对于同一项，排序键将被评估多次，所以它应该始终返回相同的值。你应该投影到一个临时匿名类型中来保存带有项目的随机值，按照这个随机值进行排序，然后再次投影以提取原始项目。 - Thomas Levesque

-1：不仅不稳定，即使它能够及时终止，得到的分布结果也会相当偏差。 - Thomas Eding

Answer 3

根据您的描述，我了解到您需要一个包含100个整数值的数组，范围从1到100，且不包含重复数字。如果这些数字是整数，则无需生成随机数字，因为所有可能的数字都在数组中。因此，只能随机排列数字的顺序。

使用Linq和Jesper Palm的方法，结合Thomas Levesque的方法，以下语句将给出您所需的数组。

Random rnd = new Random();
var randomNumbers = Enumerable.Range(1, 100)
                              .Select(x => new { val = x, order = rnd.Next() })
                              .OrderBy(i => i.order)
                              .Select(x => x.val)
                              .ToArray();

该方法非常快，绝对比任何比较操作都更有效率。

解释上面的内容给原始的发帖者，见下面的评论：

- Enumerable.Range(1, 100)创建一个范围在1到100之间的整数。 - .Select(x => new { val = x, order = rnd.Next() })创建一个新的临时对象，保存值和顺序位置，该位置由随机数确定。 - .OrderBy(i => i.order)按其顺序位置对临时对象进行排序。 - .Select(x => x.val)选择临时对象的值，将其转换回int。 - .ToArray()将所有东西再次转换为数组。

使用的语法是LINQ，它在.NET 3.5中可用。对于旧版本，您必须自己实现它，这更加复杂而且相当冗长。

根据Eric的评论：如果需要洗牌，可以按以下方式编写代码。

var list = myInputList;
var result = list.Select(x => new { val = x, order = rnd.Next() })
                 .OrderBy(i => i.order)
                 .Select(x => x.val)
                 .ToArray();

- AxelEckenberger

---

谢谢大家的回答，但是请您看一下我的想法。顺便问一下，在那个灰色框中如何添加代码？我在这里是个新手。另外，我想指出我只是一个 C# 的新手，只有几个月的经验。还有，我甚至不知道你们在这里呈现的一些东西是什么，像 Enumerable.Range，那一定是范围。Order by 肯定是排序。但我想这段代码将会按照数组中所有数字的顺序进行排序，而我想要实现的概念不是这个。我想创建一个包含 100 个元素，数字在 1 到 100 之间且顺序随机的随机数组。 - ShallowHeart

@ShallowHeart，我认为你没有理解重点。这段代码将数字从1到100取出，然后以随机确定的顺序进行“排序”。这是一种常用的洗牌技术。 - Eric Lippert

@Obalix，你的回答节省了我很多时间。你能告诉我如果我想要得到一个包含30个数字的数组，其中最大范围是变化的，我需要做什么吗？我使用了你的代码片段生成了完整范围的随机数数组，并将所需的前30个元素存储在我的数组中。如何修改这段代码以将其纳入，以减少循环时间。 - Jerin

Answer 4

这是一个天真的实现：

int[] values = new int[100];
Random random = new Random();
for(int i = 0; i < values.Length; i++)
{
    int v;
    do
    {
        v = random.Next(100) + 1;
    } while (Array.IndexOf(values, v) != -1)
    values[i] = v;
}

但这样做效率相当低，尤其是在数组末尾...

更好的解决方案是考虑到，由于你想要从1到100之间的100个不同随机值，因此你的数组最终将包含从1到100的所有可能值。所以你只需要生成这些值的序列，并对其进行“洗牌”：

int[] values = Enumerable.Range(1, 100).ToArray();
Random random = new Random();
for(int i = values.Length - 1; i > 0; i--)
{
    int j = random.Next(i + 1);
    int tmp = values[i];
    values[i] = values[j];
    values[j] = tmp;
}

---

编辑：更好的方法，适用于不太具体的情况：

T[] RandomCombinationWithNoRepeat<T>(IEnumerable<T> itemsToPickFrom, int numberOfItemsToPick)
{
    // Copy original items to pick from, because we need to modify it
    List<T> itemsCopy = new List<T>(itemsToPickFrom);
    T[] array = new T[numberOfItemsToPick];
    Random random = new Random();
    for(int i = 0; i < numberOfItemsToPick; i++)
    {
        // Pick item and remove it from list
        int index = random.Next(itemsCopy.Count);
        array[i] = itemsCopy[index];
        itemsCopy.RemoveAt(index);
    }
    return array;
}

在您的情况下，您应该像这样使用它：

int[] result = RandomCombinationWithNoRepeat(Enumerable.Range(1, 100), 100);

- Thomas Levesque

---

我更倾向于寻找一个面向对象的解决方案。我更多地考虑面向对象编程，就像这样的代码：[code] public void FillArray(int[]A, int range) { for (int I = 0; I < A.Length; I ++ A[I] = ValidNumber(T,I,Range) } [/code]在这个小想法之后，我卡住了。毕竟，我也非常严格地编码，将输入、处理和输出分别放在不同的类中。 - ShallowHeart

我认为 List<T> 没有 Length 属性，你可能想要使用 Count。 - Philippe Lavoie

Answer 5

根据我的理解，您需要一个包含随机数字的整数集合。我假设使用int数组或int列表没有区别。 这里是一个简单完整的方法，可以实现您所描述的功能。
using System; using System.Collections.Generic; System.Text;

namespace FillRandom { class Program { static void Main(string[] args) { int minValue = 1; int maxValue = 100; //创建一个容量为100的int列表 List array = new List(100);

        FillArray(array, minValue, maxValue, array.Capacity);

        //print out all values in the array
        foreach (int i in array)
        {
            Console.WriteLine(i);
        }
    }

    private static void FillArray(List<int> array, int minValue, int maxValue, int capacity)
    {
        int count = 0;
        while (array.Count != capacity - 1)
        {
            Random rnd = new Random();
            int value = rnd.Next(minValue, maxValue);
            if (!array.Contains(value))
            {
                array.Add(value);
            }
            count++;
        }
        //print out the number of times the looping occurs
        Console.WriteLine("count: "+count);
    }        
}

}

你可以创建一个控制台项目并试一试。

- Blithe

---

Eric是完全正确的，这真的是一个坏主意，我试图使用“count”来打印出来。;) 无论如何，有趣的发现是，如果每次创建一个新的Random对象（大约100k到200k循环），那么填充数组实际上会更加困难，但是如果使用相同的对象，则只需要大约500次。 - Blithe