C#中的随机数生成器 - 唯一值

Question

我正忙着在C#中编写一个数组.我可以用随机生成器来填充它,但现在我的问题是如何做到这一点,但我可以检查数值是否已经在数组中,如果是这样,生成一个新的值

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

重要的PLZ工作继续我的想法

我的想法

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的随机顺序

Answer 1

我该怎么做,但我可以检查数值是否已经在数组中,如果是这样,生成一个新的值

你永远不会这样做,因为这是一个非常糟糕的主意.

为了说明为什么这是一个糟糕的想法,请考虑同一问题的另一个版本:通过以下过程将一百万个数字排序为随机顺序:

1. 选择一到一百万的数字.
2. 检查它是否已在列表中.
3. 如果是,请返回步骤1
4. 否则,将该号码添加到列表中.
5. 列表上有一百万个项目吗？如果是的话,你就完成了.如果没有,请返回步骤1.

显然,这是有效的.这是个好主意吗？我们假设你差不多完成了.该清单上有999999件物品.唯一缺少的项目是857313.你做什么？您可以选择一个随机数,例如12.现在,检查列表中的999999个项目,看看它们中是否有12个.12可能是您选择的第一个数字之一,因此可能很快找到它.或者它可能是最后一个,所以需要很长时间.平均而言,将需要500000次检查以查看列表中是否有12个.它是,因为列表中只缺少一个数字.

12没有成功.回到开头.选择另一个随机数,比如53259.列表上有这个吗？另有50万支票.

继续这样做,直到你生成857313,每百万次尝试就会发生一次.

因此,平均而言,将最后一项放在列表中需要500000 x 1000000 =五千亿比较.它可能会更多.可能需要几万亿次比较.或者你可能会很幸运,需要一个.但平均而言,有五万亿的比较.

这是生成列表随机排序的可怕方法.

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

(1)制作一个可以对给定排序功能的列表进行排序的设备.提供基于随机种子的稳定排序.

请注意,您应该不通过使当被问及返回随机结果的方法产生一个随机排序"比B A大？" 这是一个不稳定的顺序; 许多排序算法都基于稳定的排序顺序,并且在给定不稳定的排序顺序时将进入无限循环或具有其他不良行为.

这个算法是O(n lg n),具有很好的特性,很容易写出标准部分,正如其他答案所示.对于典型实现中的小列表,它也非常快.

(2)随机选择源列表中的索引项,将其从源列表中删除,并将其放在目标列表中.

后者被称为Knuth Shuffle或Fischer-Yates Shuffle,它是一种非常快速的算法.您可以"就地"执行此操作,将现有数组变为洗牌顺序,或者创建新列表.它还有一个很好的属性,你可以"支付游戏费用",根据需要改变列表的"顶部".如果你有一百万件要洗牌,但你只需要前一百件,你可以计算出前一百件的排序顺序并称之为好.

Answer 2

以下将以随机顺序生成数字为1-100的数组.

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

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();