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

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

如何在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的arrays上进行(当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的Narrays的初始化。考虑到这一点,我认为它变得相当很明显,为M == N运行此算法,然后截断结果(可能丢弃大部分)比仅仅以原始forms运行此算法获得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值,差异可以忽略不计。

在您的示例中(选择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)选择随机元素。

简单地生成随机数并查看它们是否正常是解决此问题的一种不好的方法。 这种方法采用所有可能的值,将它们混洗,然后进入前十。 这直接类似于改组一副牌并处理顶部。

 #include  #include  #include  #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 

有关更多信息,请参阅comp.lang.c FAQ列表问题13.19进行改组, 问题13.16有关生成随机数。

我认为这样做(我没有尝试构建它,因此语法错误留给了读者修复)。 可能有更优雅的方式,但这是蛮力解决方案:

 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; } 

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

这打开了(随机;))你永远不会得到一个不在数组中的数字的可能性。 因此,您应该计算您检查数字是否已经在数组中的次数,如果计数超过MAX_DUPLICATE_COUNT,则抛出exception左右:)(编辑,看到你在C.忘记exception部分:)返回错误代码:P)

一个快速的解决方案是创建一个掩码数组,其中包含初始化为零的所有可能数字,并在生成该数字时设置一个条目

 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; } } 

这是O(M)平均时间方法。

方法:如果M <= N / 2,使用程序S(M,N)(下面)生成结果数组R,并返回R.如果M> N / 2,使用程序S(NM,N)生成R,然后计算X = {1..M}\R [ X = {1..M}\R的补集],用Fisher-Yates shuffle [在时间O(M)]中随机抽取X,并返回X.

在M> N / 2的情况下,其中O(M)== O(N),有几种快速计算补码的方法。 在下面显示的代码中,为简洁起见,我仅包括在main()中内联编码的过程S(M,N)的示例。 Fisher-Yates shuffle是O(M)并且在相关问题#196017的主要答案中说明。 其他以前的相关问题: #158716和#54059 。

当M ,从中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):[此程序的主体是在下面的代码中注释“Gen 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://stackoverflow.com/questions/1608181/ #include  #include  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=0); L[i] = H[h]; H[h] = i; } // Print results for (j=i=0; i66) j = printf ("\n"); } printf ("\ncxc %d\n", cxc); return 0; } 

我喜欢Floyd算法。

但是我们可以把所有随机数从0M (不是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); 

分别生成第一个和第二个数字。 如果需要,稍后将它们洗牌。 (来自内存的语法)

 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

或者,您需要保持数字排序( O(n log n) ),以便可以快速检查新生成的状态( O(log n) )。