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

Question

这个问题已经在这里有了答案:




已关闭8年。

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时最有用。但是，此算法不需要您的额外内存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的[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排序的某种“影响”。例如，很明显，如果选择的结果只能是结果数组的最后一个成员。如果不希望的结果对结果的这种“污染”是 Not Acceptable ，则可以像Khuth算法一样对结果的 vektor数组进行随机混洗。

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

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