O(1) 时间复杂度内生成不重复的随机数？

Question

O(1) 时间复杂度内生成不重复的随机数？

algorithmmathrandomlanguage-agnostic

197

我想生成0到1000之间不重复的独特随机数（即6不会出现两次），但是不想使用类似于O(N)搜索先前值的方法来实现。这是否可能？

- dicroce

4

这不是与 https://dev59.com/3nVC5IYBdhLWcg3w4VNy 相同的问题吗？ - jk.

2

0 是否在 0 和 1000 之间？ - Pete Kirkham

6

如果您禁止任何超出常数时间的事物（例如时间或内存中的 O(n)），那么下面许多答案都是错误的，包括被接受的答案。 - jww

11

警告！下面给出的许多答案并未产生真正的随机序列，速度比O(n)慢或者有其他缺陷！在使用任何这些答案之前或试图自己构造它们之前，请务必阅读http://www.codinghorror.com/blog/archives/001015.html！ - ivan_pozdeev

根据http://meta.stackoverflow.com/questions/334325/a-few-intersecting-questions-about-picking-k-elements-of-n的规定，将其标记为低劣的重复内容。 - ivan_pozdeev

显示剩余2条评论

22个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paparazzo · Answer 1

费舍尔-耶茨算法

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

实际上它是O(n-1)，因为你只需要交换最后两个
这是C#

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}

- Grog Klingon · Answer 2

有人发布了“在Excel中创建随机数”的帖子。我正在使用这个方法。创建一个包含两个部分str.index和str.ran的结构体；对于10个随机数，创建一个由10个结构体组成的数组。将str.index从0到9设置为不同的随机数。

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

按照arr[i].ran中的值对数组进行排序。 str.index现在是随机顺序。以下是C代码：

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}