C编程语言中整数数组中的唯一随机数

Question

可能重复:
O(1)中的唯一随机数？

如何在C中填充具有唯一值(无重复项)的整数数组？

int vektor[10];   

for (i = 0; i < 10; i++) {
    vektor[i] = rand() % 100 + 1;
}

//No uniqueness here

Answer 1

有几种方法可以解决您的问题,每种方法都有自己的优缺点.

首先我要注意你已经有很多响应做了以下事情:它们生成一个随机数,然后以某种方式检查它是否已经在数组中使用,如果它已经被使用,它们只是生成另一个编号,直到他们找到一个未使用的.这是一个天真的,事实是,严重缺陷的方法.问题在于数字生成的循环反复试验性质("如果已经使用,请再试一次").如果数值范围(例如,[1..N])接近所需数组的长度(例如,M),那么到最后算法可能会花费大量时间来尝试查找下一个数字.如果随机数生成器甚至有点破碎(比如说,从不生成一些数字,或者很少生成),那么使用N == M,算法可以保证永远循环(或者很长时间).一般来说,这种反复试验的方法是无用的,或者充其量是有缺陷的.

这里已经提出的另一种方法是在大小为N的数组中生成随机置换.随机置换的想法很有希望,但是在大小为N的阵列上进行(当M << N时)肯定会产生比光更多的热量.比喻地说.

例如,在Bentley的"Programming Pearls"(其中一些来自Knuth)中可以找到解决这个问题的好方法.

• Knuth算法.这是一个非常简单的算法,复杂度为O(N)(即数值范围),这意味着当M接近N时它最有用.但是,除了vektor数组之外,这个算法不需要任何额外的内存,与已经提供的具有排列的变体相反(意味着它需要O(M)存储器,而不是像这里建议的其他基于排列的算法的O(N)).后者使其成为一种可行的算法,即使对于M << N个案例.

该算法的工作原理如下:迭代从1到N的所有数字并选择当前数字的概率rm / rn,其中rm我们仍需要找到rn多少个数字,以及我们仍需要迭代的数量.这是您的案例的可能实施

#define M 10
#define N 100

int in, im;

im = 0;

for (in = 0; in < N && im < M; ++in) {
  int rn = N - in;
  int rm = M - im;
  if (rand() % rn < rm)    
    /* Take it */
    vektor[im++] = in + 1; /* +1 since your range begins from 1 */
}

assert(im == M);

在这个循环之后,我们得到一个数组,其中按vektor随机选择的数字按升序排列."升序"位是我们在这里不需要的.因此,为了"修复"我们只是对元素进行随机排列,vektor我们就完成了.注意,这是一个O(M)排列,不需要额外的内存.(我省略了排列算法的实现.这里已经给出了很多链接.).

如果仔细观察这里提出的基于排列的算法,这些算法对长度为N的数组进行操作,你会发现它们中的大多数都是非常相同的Knuth算法,但重新制定了M == N.在这种情况下,上面的选择周期将选择[1..N]范围内的每个数字,概率为1,有效地转换为数字1到N的N阵列的初始化.考虑到这一点,我认为它变得相当显而易见的是,运行此算法M == N然后截断结果(可能丢弃其中的大部分)比仅以原始形式运行此算法获得M的原始值并立即获得结果而没有任何截断更为明显.

• Floyd算法(见这里).这种方法具有约O(M)的复杂度(取决于所使用的搜索结构),因此当M << N时更适合.这种方法跟踪已经生成的随机数,因此需要额外的内存.然而,它的美妙之处在于它没有进行任何可恶的试错迭代,试图找到一个未使用的随机数.保证该算法在每次调用随机数发生器后生成一个唯一的随机数.

这是针对您的案例的可能实现.(有不同的方法来跟踪已经使用的数字.我只会使用一个标志数组,假设N不是非常大)

#define M 10
#define N 100    

unsigned char is_used[N] = { 0 }; /* flags */
int in, im;

im = 0;

for (in = N - M; in < N && im < M; ++in) {
  int r = rand() % (in + 1); /* generate a random number 'r' */

  if (is_used[r])
    /* we already have 'r' */
    r = in; /* use 'in' instead of the generated number */

  assert(!is_used[r]);
  vektor[im++] = r + 1; /* +1 since your range begins from 1 */
  is_used[r] = 1;
}

assert(im == M);

为什么上述工作并不是立竿见影的.但它的确有效.来自[1..N]范围的恰好M个数将被均匀分布挑选.

注意,对于大N,您可以使用基于搜索的结构来存储"已使用"的数字,从而获得具有O(M)内存要求的漂亮的O(M log M)算法.

(关于这个算法有一点是这样的:虽然结果数组不会被排序,但原始1..N排序的某些"影响"仍会出现在结果中.例如,很明显数字N,如果选择的,只能是结果数组的最后一个成员.如果由于非预期的排序导致的结果"污染"是不可接受的,那么结果vektor数组可以随机改组,就像在Khuth算法中一样.

注意在这两个算法的设计中观察到的非常关键的一点:它们从不循环,试图找到一个新的未使用的随机数.从实际的角度来看,任何使用随机数进行试错迭代的算法都是有缺陷的.此外,这些算法的内存消耗与M相关,而与N无关

对于OP我会推荐Floyd的算法,因为在他的应用程序中,M似乎比N小得多,并且它不(或可能不)需要额外的排列通过.然而,对于如此小的N值,差异可以忽略不计.

Answer 2

在您的示例中(选择1到100之间的10个唯一随机数),您可以创建一个数字为1到100的列表,使用随机数生成器对列表进行混洗,然后从列表中获取前10个值.

int list[100], vektor[10];
for (i = 0; i < 100; i++) {
    list[i] = i;
}
for (i = 0; i < 100; i++) {
    int j = i + rand() % (100 - i);
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}
for (i = 0; i < 10; i++) {
    vektor[i] = list[i];
}

根据下面的cobbal评论,最好只说:

for (i = 0; i < 10; i++) {
    int j = i + rand() % (100 - i);
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;

    vektor[i] = list[i];
}

现在设置列表是O(N)但是O(M)选择随机元素.