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

Z时代
2024-01-10
分类：问答

如何在C中使用唯一值（无重复）填充整数数组？

int vektor[10];
for (i = 0; i < 10; i++) {
    vektor[i] = rand() % 100 + 1;
}
//No uniqueness here

回答：

解决问题的方法有几种，每种都有其优点和缺点。

首先，我想指出的是，您已经获得了很多响应，它们执行以下操作：它们生成一个随机数，然后以某种方式检查它是否已在数组中使用，如果已经使用过，则仅生成另一个直到找到未使用的编号。这是一种幼稚的方法，说实话，是一种严重错误的方法。问题在于数字生成的周期性反复试验性质（“如果已使用，请重试”）。如果数值范围（例如[1..N]）接近所需数组的长度（例如M），那么到最后，算法可能会花费大量时间来尝试查找下一个数字。如果随机数生成器有点破损（例如，从不生成某个数字，或者很少生成该数字），然后使用N

== M保证算法永远循环（或很长一段时间）。通常，这种反复试验方法无用或充其量是有缺陷的。

这里已经介绍的另一种方法是在大小为N的数组中生成随机排列。随机排列的想法是一种很有前途的方法，但是在大小为N的数组上进行排列（当M <<

N时，肯定会产生比光更多的热量），比喻地说。

例如，可以在Bentley的“ Programming Pearls”中找到很好的解决方案（其中一些取自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的原始值以其原始形式运行该算法并立即获得结果而没有任何截断相比，运行该算法然后将其截断（可能丢弃其中的大部分结果）的意义要小得多。

（请参阅此处）。此方法的复杂度约为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);