在范围内生成N个随机且唯一的数字

11
使用C#在给定范围内生成N个唯一数字的高效方法是什么?例如,生成6个介于1和50之间的唯一数字。一种懒惰的方法是仅仅在循环中使用Random.Next()并将该数字存储在数组/列表中,然后重复执行并检查它是否已存在等。是否有更好的方法来生成一组随机但唯一的数字? 为了增加更多的背景信息,我希望使用它们的索引从一个集合中选择N个随机项。
谢谢

可能是从子集中获取五个唯一的随机数的重复问题。 - Tim Stone
1
@drachenstern:今天有点敏感了,不是吗?@Tim - 对不起,我没有搜索“子集”关键字,结果得到了为什么随机数生成很困难的结果。谢谢提供链接。 - Skoder
我不这么认为。我认为这个问题已经得到很好的解决了。显然还有其他人同意我的看法。 - jcolebrand
1
@drachenstern - 和你所说的无关。只是想知道是否真的需要使用讽刺。 - Skoder
7个回答

17

取一个包含50个元素的数组:{1, 2, 3, .... 50},使用标准的随机打乱算法对其进行乱序处理。修改后的数组前六个元素就是你要找的结果。祝好运!


@HPT:在那种情况下,最好保留一组已有数字。但是在这种情况下,当数字很小的时候,我认为我的解决方案还不错。 - Armen Tsirunyan
2
@armen:正确的解决方案与好的解决方案是不同的。你也可以像问题所述一样编写一个随机生成器,但那并不是解决方案。 - user415789
@HPT:至少我的解决方案具有可预测的运行时间。 - Armen Tsirunyan
1
至少使用 O(n) 的内存和 O(n) 的运行时间!这里的 n 表示范围。 - user415789
1
对于从50个数字中选择6个数字的问题,这个解决方案可能是可以接受的,因为随机排序50个数字并不会很耗时。但是,同样地,简单的记住和丢弃重复项的方法也是一样的,因为重复的概率并不高。对于一个更有效的答案(无需事先排序,保证不会出现重复项),你需要使用我的答案中提到的Fisher-Yates洗牌算法,但在这里实际上可能并不需要 - 你必须根据问题来定位你的解决方案。 - paxdiablo

11

对于从50中选6个数字,我不太确定是否需要担心效率,因为重复出现的机会相对较低(根据我的草稿计算,总体上约为30%)。你可以很容易地记住之前生成的数字并将其丢弃,类似以下的伪代码:

n[0] = rnd(50)
for each i in 1..5:
    n[i] = n[0]
while n[1] == n[0]:
    n[1] = rnd(50)
while n[2] == any of (n[0], n[1]):
    n[2] = rnd(50)
while n[3] == any of (n[0], n[1], n[2]):
    n[3] = rnd(50)
while n[4] == any of (n[0], n[1], n[2], n[3]):
    n[4] = rnd(50)
while n[5] == any of (n[0], n[1], n[2], n[3], n[4]):
    n[5] = rnd(50)
然而,随着选取范围从6-from-50扩展至48-from-50或6-from-6,会出现问题。因为随着可用数字的池子越来越小,重复的概率变得越来越高。对于这种情况,一个非常有效的解决方案是使用Fisher-Yates算法,它可以给你一个值的子集,并且零概率出现重复(并且没有不必要的预先排序)。
dim n[50]                 // gives n[0] through n[9]
for each i in 0..49:
    n[i] = i              // initialise them to their indexes
nsize = 50                // starting pool size
do 6 times:
    i = rnd(nsize)        // give a number between 0 and nsize-1
    print n[i]
    nsize = nsize - 1     // these two lines effectively remove the used number
    n[i] = n[nsize]

通过从池中随机选择一个数字,用该池的顶部数字替换它,然后缩小池的大小,您可以获得一次洗牌而无需担心大量的初始交换。

如果数字很高,这很重要,因为它不会引入不必要的启动延迟。

例如,考虑以下基准测试,选择10个数字中的10个:

<------ n[] ------>
0 1 2 3 4 5 6 7 8 9  nsize  rnd(nsize)  output
-------------------  -----  ----------  ------
0 1 2 3 4 5 6 7 8 9     10           4       4
0 1 2 3 9 5 6 7 8        9           7       7
0 1 2 3 9 5 6 8          8           2       2
0 1 8 3 9 5 6            7           6       6
0 1 8 3 9 5              6           0       0
5 1 8 3 9                5           2       8
5 1 9 3                  4           1       1
5 3 9                    3           0       5
9 3                      2           1       3
9                        1           0       9

当您执行代码时,可以观察到所使用的池逐渐减少。由于您始终在用未使用的元素替换已使用的元素,因此您永远不会重复使用。

使用从该代码返回的结果作为索引来访问您的集合,将保证不选择重复项。


这是最佳解决方案,是我的改进版本。 - Erik Philips
如果范围非常大,将所有数字存储在内存中可能是不可能的。 - Display Name

8
var random = new Random();
var intArray = Enumerable.Range(0, 4).OrderBy(t => random.Next()).ToArray();

这个数组将包含从0到4的5个随机数字。

或者

  var intArray = Enumerable.Range(0, 10).OrderBy(t => random.Next()).Take(5).ToArray();

这个数组将会包含在0到10之间的5个随机数。

int firstNumber = intArray[0];
int secondNumber = intArray[1];
int thirdNumber = intArray[2];
int fourthNumber = intArray[3];
int fifthNumber = intArray[4];

第一个解决方案非常简洁。谢谢! - Chris Rae

6

对于大量的唯一数字,请将它们放入一个列表中。

        Random random = new Random();
        List<int> uniqueInts = new List<int>(10000);
        List<int> ranInts = new List<int>(500);
        for (int i = 1; i < 10000; i++) { uniqueInts.Add(i); }

        for (int i = 1; i < 500; i++)
        {
            int index = random.Next(uniqueInts.Count) + 1;
            ranInts.Add(uniqueInts[index]);
            uniqueInts.RemoveAt(index);
        }

随机生成一个从1到myInts.Count的数字。存储myInt的值并将其从List中删除。无需打乱列表,也不需要查看该值是否已存在。


2
从列表中删除数字(无论您想使用哪个IEnumerable)使其成为唯一的,如果它不存在,则无法从列表中获取它... 再次针对大量唯一数字集合,这样做更快,因为您不需要查找可能存在或不存在的数字。 - Erik Philips
1
对我来说很好用。只有一个小bug:应该是uniqueInts.RemoveAt(index);而不是uniqueInts.Remove(index); - AyKarsi
@AyKarsi,那是非常重要的笔记,谢谢!(已更新) - Erik Philips

1

不要使用 List,而是使用 Dictionary!!


另外,您应该检查是否成功添加了N个值。显然,如何检查是否已将新值添加到字典中! - user415789
谢谢的建议。我想对于更大的集合来说,使用字典会更好。 - Skoder

0

如果有人需要帮助,我更喜欢分配最少数量的项目。在下面,我使用了一个HashSet,它确保新项目是唯一的。这也适用于非常大的集合,直到HashSet的限制。

    public static IEnumerable<int> GetRandomNumbers(int numValues, int maxVal)
    {
        var rand = new Random();
        var yieldedValues = new HashSet<int>();

        int counter = 0;
        while (counter < numValues)
        {
            var r = rand.Next(maxVal);
            if (yieldedValues.Add(r))
            {
                counter++;
                yield return r;
            }
        }
    }

-1

生成1到40之间的唯一随机数:

输出已确认:

class Program

{
    static int[] a = new int[40];
    static Random r = new Random();
    static bool b;
    static void Main(string[] args)
    {
        int t;
        for (int i = 0; i < 20; i++)
        {
        lab:  t = r.Next(1, 40);
            for(int j=0;j<20;j++)
            {

                if (a[j] == t)
                {
                    goto lab;
                }
            }

            a[i] = t;
            Console.WriteLine(a[i]);



        }
        Console.Read();
    }


}

样例输出:

7 38 14 18 13 29 28 26 22 8 24 19 35 39 33 32 20 2 15 37


6
效率极低的解决方案...尤其是已经有更好的答案了。您还有未使用的属性,并且使用了Goto!!!为什么? - bPratik

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接