整数数组中独特随机数生成

Question

可能是重复的问题:
Unique random numbers in O(1)?

如何在C语言中用不重复的值（没有重复）填充整数数组？

int vektor[10];   

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

//No uniqueness here

- Chris_45

---

顺便提一下，仅分配数组索引就可以满足“唯一值”的要求，但并未解决隐含的“唯一随机值”的问题。 - Otis

不，这不是。只选择M个中的N个（如上面的“在100中选择10个”）是一个重要细节。 - AnT stands with Russia

Answer 1

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

首先，我想指出你已经得到了相当多的回答，这些回答都是生成随机数，然后以某种方式检查它是否已在数组中使用过，如果已被使用，则继续生成另一个数字，直到找到未使用的数字。

这是一种天真而且说实话，严重有缺陷的方法。问题在于数字生成的循环试错性质（“如果已使用，请重试”）。如果数字范围（如[1..N]）接近所需数组的长度（如M），那么算法可能会花费大量时间来寻找下一个数字。如果随机数生成器有一点点问题（比如从不生成某个数字或极少生成该数字），那么当N==M时，该算法保证会无限循环（或者循环非常长的时间）。通常这种试错方法是毫无用处的，或者充其量也只是一个有缺陷的方法。

这里已经介绍了另一种方法，即在大小为N的数组中生成随机排列。 随机排列的想法很有前途，但是在大小为N的数组上执行它（当M << N时）肯定会造成更多的麻烦而不是解决问题。

例如，在Bentley的“编程珠玑”中可以找到此问题的好解决方案（其中一些取自Knuth）。

---

• Knuth算法。 这是一个非常简单的算法，其复杂度为O（N）（即数字范围），这意味着当M接近N时它最有用。然而，与已经提供的带置换的变体相比（意味着它只需要你的vektor数组本身没有额外的内存），该算法不需要任何额外的内存。后者使它成为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 算法 （见这里）。该方法的复杂度大约为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 log M)算法，其内存需求为O(M)。

（这种算法有一个问题：虽然结果数组不会被排序，但原始的1..N顺序在结果中仍会有一定的“影响”。例如，如果选择了数字N，则它只能成为结果数组的最后一个成员。如果不接受意外顺序的“污染”，则可以像Khuth算法一样对结果的vektor数组进行随机重排。）

---

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

对于OP，我推荐使用Floyd算法，因为在他的应用程序中，M似乎远小于N，并且不需要额外的排列。但是，对于如此小的N值，差异可能是可以忽略的。

- AnT stands with Russia

---

我不同意你的说法，“试错法”是无用的。即使N==M时，朴素的试错算法也有很强的保证（它以高概率在O(nlgn)时间内完成）。例如，当M<N/2时，它以高概率在O(n)时间内完成。 - Keith Randall

我只能说，这个保证在实践中并不可靠。对于N==M的情况，使用不良或低质量的“rand()”函数陷入无限循环的可能性相当高（即使使用好的“rand()”函数，最后几个元素的搜索时间也更长）。我不知道你如何合理地期望在实践中达到O(n lg n)的效率。在理想的世界里，也许可以... - AnT stands with Russia

O(n lg n) 的时间复杂度可能来自于类似于（令人惊讶的）收集优惠券问题的分析：http://en.wikipedia.org/wiki/Coupon_collector%27s_problem。虽然较差的 rand() 可能会使情况变得更糟，但只要 rand() 实际上命中了所有值，它应该只会偏离一个常数：我不知道任何 rand() 实现不满足这一点。 - ShreevatsaR

或者，对于收集优惠券问题的（简短）解决方案的非正式总结：确实，在列表末尾附近，您可能需要调用rand()来查找新元素O(n)次，但这仅适用于其中约O(log n)个元素，因此一切都可以解决。是否O(n log n)实际上足够好是另一回事：不要低估那些对数因子！ - ShreevatsaR

我也不同意试错法是“无用”的说法，因为大多数可靠的爬山算法在某个阶段都会使用它。一个有趣的例子是恩尼格玛M4项目，在分布式网络中使用爬山算法破解插线板密码。然而，+1，这显然是问题的最佳答案。 - Tim Post

哈哈，看起来我今天在面试中从零开始创建了 Floyd 算法。不错的信息。+1 - Grozz

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)。

- mob

---

我同意 - 请参考eyalim链接中的被接受的答案。 - mob

随机数机制存在一些微小但不一定可以忽略的偏差，但如果你解决了这个问题，这是一种很好的技术。请注意中间循环中的上限；你只能将list[99]与其自身交换，虽然你的代码已经实现了这一点，但有点“浪费”。 - Jonathan Leffler

@mobrule：链接中的被接受答案仅适用于需要从1000个数字中获取1000个数字的情况。对于OP的问题，该方法只会产生更多的热量而不是光亮。 - AnT stands with Russia

我有10个数字，我想要随机选择这10个数字，我使用了int randomNumber=arc4random()%10; 它可以生成随机数字，但是会重复。请帮帮我。 - Vineesh TP

非常聪明的方法！！ 如果您正在使用ArrayList，那么在Java中最有用的方法是通过Collection进行洗牌。 - Chaitanya Chandurkar

Answer 3

我认为这个就可以了（我没有尝试过构建它，所以语法错误应该留给读者作为练习来修复）。可能还有更优雅的解决方案，但这是一种粗暴的解决方法：

int vektor[10];    
int random;
int uniqueflag;
int i, j

for(i = 0; i < 10; i++) {
     do {
        /* Assume things are unique... we'll reset this flag if not. */
        uniqueflag = 1;
        random = rand() % 100+ 1;
        /* This loop checks for uniqueness */
        for (j = 0; j < i && uniqueflag == 1; j++) {
           if (vektor[j] == random) {
              uniqueflag = 0;
           }
        }
     } while (uniqueflag != 1);
     vektor[i] = random;
}

- Chris J

---

任何使用“再试一次”方法的算法都具有非常有限的实际价值。实际上，我会说洗牌方法更好，但是可以更好地实现洗牌（请参见我的回复中的Knuth方法）。 - AnT stands with Russia

Answer 4

通常来说，仅仅生成随机数并验证它们是否符合要求是解决这个问题的一种不好的方法。这种方式会取出所有可能的值并将它们混合在一起，然后取前十个。这就像是洗牌并从牌堆顶端发牌。

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

#define randrange(N) rand() / (RAND_MAX/(N) + 1)

#define MAX 100        /* Values will be in the range (1 .. MAX) */
static int vektor[10];
int candidates[MAX];

int main (void) {
  int i;

  srand(time(NULL));   /* Seed the random number generator. */

  for (i=0; i<MAX; i++)
    candidates[i] = i;

  for (i = 0; i < MAX-1; i++) {
    int c = randrange(MAX-i);
    int t = candidates[i];
    candidates[i] = candidates[i+c];
    candidates[i+c] = t;
  }

  for (i=0; i<10; i++)
    vektor[i] = candidates[i] + 1;

  for (i=0; i<10; i++)
    printf("%i\n", vektor[i]);

  return 0;
}

更多信息，请参见comp.lang.c FAQ列表问题13.19了解洗牌和问题13.16关于生成随机数。

- Tim

Answer 5

一个快速的解决方案是创建一个所有可能数字值为零的掩码数组，并在生成该数字时设置一个条目。

int rand_array[100] = {0};
int vektor[10];   
int i=0, rnd;
while(i<10) {
    rnd = rand() % 100+ 1;
    if ( rand_array[rnd-1] == 0 ) {
        vektor[i++] = rnd;
        rand_array[rnd-1] = 1;
    }
}

- Amro

Answer 6

分别生成第一位和第二位数字。 如果需要，稍后再进行洗牌。（语法来自记忆）

int vektor[10];
int i = 0;

while(i < 10) {
  int j = rand() % 10;
  if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;}
}

不过，这些数字之间将会有n的差距，其中0 < n < 10。

否则，你需要保持这些数字排序（O(n log n)），以便新生成的数字可以快速地被检查是否存在（O(log n)）。

- Milind C

Answer 7

这里有一个O(M)平均时间复杂度的方法。

方法：如果M ≤ N/2，则使用过程S(M,N)（如下）生成结果数组R，并返回R。如果M > N/2，则使用过程S(N-M,N)生成R，然后计算X = {1..M}\R [在{1..M}中R的补集]，用Fisher-Yates shuffle [在O(M)时间内]对X进行洗牌，然后返回X。

在O(M) == O(N)且M > N/2的情况下，有几种快速计算补集的方法。以下代码中，为了简洁起见，我只包括了一个内联编码在main()函数中的S(M,N)过程示例。Fisher-Yates Shuffle是O(M)，并在相关问题#196017的主答案中进行了说明。其他之前相关的问题：#158716和#54059。

当M < N/2时，S(M,N)需要O(M)时间而不是O(N)时间的原因是，正如收集优惠券问题中所述，期望E(t_k)是kH_k，从中可以得出E(t_{k/2}) = k(H_k - H_{k/2})或大约为k*(ln(k)-ln(k/2)+O(1)) = k*(ln(k/(k/2))+O(1)) = k*(ln(2)+O(1)) = O(k)。

过程S(k，N)：[此过程的主体是下面代码中“生成M个不同的随机数”注释后的十几行。] 分配并初始化三个M + 1元素整数数组H，L和V，其所有值均为-1。 对于i = 0到M-1：将随机值v放入V [i]和哨兵节点V [-1]中。 从H [v％M]中获取M个列表头之一，并跟随该列表，直到找到与v匹配的项。 如果匹配在V [-1]处，则v是一个新值； 因此更新列表头H [v％M]和列表链接L [i]。 如果匹配不在V [-1]处，则获取并测试另一个v，等等。

每个“跟随列表”步骤的预期成本为O（1），因为除了最后一步外，每个步骤的平均列表长度都小于1。（在处理结束时，M个列表包含M个元素，因此平均长度逐渐上升到正好1。）

 // randomMofN - jiw 8 Nov 2011     
 // Re: https://dev59.com/TXI-5IYBdhLWcg3w8NOB
 #include <stdlib.h>
 #include <stdio.h>
 int main(int argc, char *argv[]) {
   int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0;
   // Get M and N values
   ++par; M = 42;  if (argc > par) M = atoi(argv[par]);
   ++par; N = 137; if (argc > par) N = atoi(argv[par]);
   tM = 3*M+3;
   H = malloc(tM*sizeof(int));
   printf ("M = %d,  N = %d  %s\n", M, N, H?"":"\nmem error");
   if (!H) exit(13);
   for (i=0; i<tM; ++i)           // Init arrays to -1's
     H[i] = -1;
   L = H+M;  V = L+M;

   // Gen M distinct random numbers
   for (i=0; i<M; ++i) {
     do {
       ++cxc;                     // complexity counter
       V[-1] = V[i] = random()%N;
       h = V[i]%M;                // h = list-head index
       j = H[h];
       while (V[j] != V[i])
         j = L[j];
     } while (j>=0);
     L[i] = H[h];
     H[h] = i;
   }

   // Print results
   for (j=i=0; i<M; ++i) {
     j += printf ("%4d ", V[i]);
     if (j>66) j = printf ("\n");
   }
   printf ("\ncxc %d\n", cxc);
   return 0;
 }

- James Waldby - jwpat7

---

问题[#2394246]也与Robert Floyd的抽样算法有关，并包括讨论。 - James Waldby - jwpat7

Answer 8

我喜欢弗洛伊德算法。

但我们可以从0到M中取所有的随机数（而不是in）：

#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() % (N + 1); /* generate a random number 'r' */

  while (is_used[r])
  {
     /* we already have 'r' */
     r = rand() % (N + 1);
  }
  vektor[im++] = r + 1; /* +1 since your range begins from 1 */
  is_used[r] = 1;
}

assert(im == M);

- Hicham

Answer 9

一种方法是检查数组是否已经包含新的随机数，如果是，则创建一个新的随机数并重试。

这会打开一个（随机的 ;) ）可能性，即您永远不会得到不在数组中的数字。因此，您应该计算检查数字是否已经在数组中的次数，如果计数超过MAX_DUPLICATE_COUNT，则抛出异常或类似操作 :) （编辑，看到您在C中。忘记异常部分 :) 返回错误代码即可 :P）

- cwap

---

如果我给一个函数一个明确定义的任务和一个明确定义的解决方案，而函数返回一个“抱歉，这次我无法完成”错误代码，我会感到非常惊讶 :) - AnT stands with Russia

哈哈，是的，那看起来会很棒 :) - cwap