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

Question

This question already has answers here:

Closed 7 years ago.

Possible Duplicate:
Unique random numbers in 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时最有用。但是，此算法除了您的< cc>数组，而不是已经提供的带有置换的变体（这意味着它需要O（M）内存，而不是此处建议的其他基于置换的算法为O（N））。即使对于M << N个案例，后者也使其成为可行的算法。


该算法的工作方式如下：迭代从1到N的所有数字，并以概率vektor选择当前数字，其中rm / rn是我们仍然需要找到多少个数字，而rm是我们仍然需要多少个数字遍历。这是您的情况的可能实现

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

在此循环之后，我们得到一个数组 rn，其中填充有按升序随机选择的数字。这里不需要“升序”位。因此，为了“修复”，我们只是对 vektor的元素进行随机排列，然后完成。请注意，这是一个O（M）排列，不需要额外的内存。 （我省略了置换算法的实现。这里已经给出了很多链接。）

如果仔细查看此处提出的基于长度为N的数组的基于置换的算法，您会发现它们中的大多数几乎都是相同的Knuth算法，但针对 vektor进行了重新公式化。在这种情况下，上述选择周期将以概率1选择[1..N]范围内的每个数字，从而有效地初始化为数字1到N的N数组。考虑到这一点，我认为它变得相当很明显，对于 M == N运行此算法然后截断结果（可能会丢弃大部分结果），比对M的原始值以原始形式运行此算法并立即获得结果而没有任何截断要有意义得多。




Floyd算法（请参见 here）。此方法的复杂度约为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排序的某种“影响力”。例如，很明显，如果选择的结果只能是结果数组的最后一个成员。如果不希望的排序对结果的这种“污染”是不可接受的，则可以对结果 M == N数组进行随机混洗，就像在Khuth算法中一样。



请注意在设计这两个算法时观察到的非常关键的一点：它们永远不会循环，试图找到一个新的未使用的随机数。从实用的角度来看，任何使用随机数进行反复试验迭代的算法都是有缺陷的。此外，这些算法的内存消耗与M无关，与N无关

我会向OP建议Floyd算法，因为在他的应用中M似乎比N小很多，并且它不需要（或可能不需要）额外的遍历来进行排列。但是，对于如此小的N值，差异可能可以忽略不计。