如何有效地生成0和上界N之间的K个非重复整数列表

这个问题给出了所有必要的数据：在给定区间[0，N-1]内生成一个K个非重复整数序列的有效algorithm是什么。 如果K很大，并且接近N，那么这个微不足道的algorithm（生成随机数，在将它们添加到序列之前，查看它们是否已经存在）是非常昂贵的。

在从链表中有效地select一组随机元素中提供的algorithm似乎比必要的更复杂，并且需要一些实现。 我刚刚发现了另一个algorithm，只要你知道所有的相关参数，就可以做得很好。

Answer 1

Python库中的随机模块使其非常简单而有效：

from random import sample print sample(xrange(N), K) 

sample函数返回从给定序列中select的K个唯一元素的列表。
xrange是一个“列表模拟器”，即它的行为就像xrange连续的数字，而不是在内存中创build它，这使得它像这样的任务超快。

Answer 2

在“计算机编程的艺术”第2卷：“数字algorithm”第三版中 ，Knuth描述了以下select抽样algorithm：

algorithmS（select抽样技术）。 从一组N中随机地selectn个logging，其中0 <n≤N。

S1。 （初始化）设置t←0，m←0.（在这个algorithm中，m代表到目前select的logging数量，t是我们处理的inputlogging总数。

S2。 [生成U.]生成一个随机数U，在0和1之间均匀分布。

S3。 [testing]如果（N-t）U≥n-m，则转到步骤S5。

S4。 [select]为样本select下一个logging，并将m和t增加1.如果m <n，则转到步骤S2; 否则样本完成，algorithm终止。

S5。 跳过下一条logging（不要包括在样本中），将t加1，然后回到步骤S2。

实现可能比描述更容易遵循。 下面是一个Common Lisp实现，从列表中selectn个随机成员：

 (defun sample-list (n list &optional (length (length list)) result) (cond ((= length 0) result) ((< (* length (random 1.0)) n) (sample-list (1- n) (cdr list) (1- length) (cons (car list) result))) (t (sample-list n (cdr list) (1- length) result)))) 

这里是一个不使用recursion的实现，它可以处理各种序列：

 (defun sample (n sequence) (let ((length (length sequence)) (result (subseq sequence 0 n))) (loop with m = 0 for i from 0 and u = (random 1.0) do (when (< (* (- length i) u) (- nm)) (setf (elt result m) (elt sequence i)) (incf m)) until (= mn)) result)) 

Answer 3

实际上，可以在空间中根据所选元素的数量，而不是所选元素的大小，而不考虑所选元素的比例。 你可以通过产生一个随机排列来做到这一点，然后像这样select它：

select一个分组密码，如TEA或XTEA。 使用XOR折叠将块大小减小到比您所选集合大两倍的最小功率。 使用随机种子作为密码的关键。 要在排列中生成元素n，请使用密码对n进行encryption。 如果输出号码不在您的设置中，请将其encryption。 重复，直到数字在集合内。 平均而言，您必须对每个生成的数字执行less于两次的encryption。 这还有一个好处，就是如果你的种子是密码安全的，你的整个排列也是如此。

我在这里更详细地写了这个。

Answer 4

下面的代码（C语言，未知来源）似乎很好地解决了这个问题：

  /* generate N sorted, non-duplicate integers in [0, max[ */ int *generate(int n, int max) { int i, m, a; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; m = 0; for (i=0; i<max; i++) { a = random_in_between(0, max - i); if (a < n - m) { g[m] = i; m ++; } } return g; } 

有没有人知道我能在这里find更多的gem？

Answer 5

生成一个数组0...N-1填充a[i] = i 。

然后洗牌第一个K项目。

洗牌：

• 开始J = N-1
• select一个随机数0...J （比如R ）
• 换a[R]与a[J]
  • 因为R可以等于J ，所以元素可以与自己交换
• 从J减去1并重复。

最后，拿K最后的元素。

这实质上是从列表中选取一个随机元素，将其移出，然后从剩下的列表中选取一个随机元素，依此类推。

在O（K）和O（N）时间工作，需要O（N）存储。

洗牌部分被称为Fisher-Yates洗牌或Knuth的洗牌 ，在“ 计算机程序devise艺术 ”第2卷中描述。

Answer 6

通过将K数存储在散列存储中来加快平凡的algorithm。 在开始之前知道K会消除插入哈希映射的所有低效率，并且您仍然可以从快速查找中获益。

Answer 7

第1步：生成您的整数列表。
步骤2：执行Knuth Shuffle 。

请注意，由于Knuth Shufflealgorithm允许您仅应用n个随机数，因此不需要随机整个列表，而n是要返回的元素的数量。 生成列表仍然需要与列表大小成比例的时间，但是您可以重新使用现有列表，以满足未来所有的混洗需求（假设大小保持不变），而不必在重新启动混洗algorithm之前对部分混洗列表进行预混洗。

Knuth Shuffle的基本algorithm是从一个整数列表开始。 然后，将第一个整数与列表中的任何数字交换，并返回当前（新）第一个整数。 然后，将第二个整数与列表中的任意数字（第一个除外）进行交换并返回当前（新）第二个整数。 然后…等…

这是一个非常简单的algorithm，但要小心在执行交换时将当前项目包含在列表中，否则将破坏algorithm。

Answer 8

油藏采样版本非常简单：

 my $N = 20; my $k; my @r; while(<>) { if(++$k <= $N) { push @r, $_; } elsif(rand(1) <= ($N/$k)) { $r[rand(@r)] = $_; } } print @r; 

这是从STDIN随机select的$ N行。 如果你不使用文件中的行，用其他东西replace<> / $ _东西，但它是一个非常简单的algorithm。

Answer 9

我的解决scheme是面向C ++的，但我相信它可以被翻译成其他语言，因为它非常简单。

• 首先，生成一个K元素的链表，从0到K
• 然后只要列表不为空，就生成一个介于0和vector大小之间的随机数
• 拿这个元素，把它推入另一个向量，并将其从原始列表中删除

这个解决scheme只涉及两个循环迭代，并没有散列表查找或sorting的任何东西。 所以在实际的代码中：

 // Assume K is the highest number in the list std::vector<int> sorted_list; std::vector<int> random_list; for(int i = 0; i < K; ++i) { sorted_list.push_back(i); } // Loop to K - 1 elements, as this will cause problems when trying to erase // the first element while(!sorted_list.size() > 1) { int rand_index = rand() % sorted_list.size(); random_list.push_back(sorted_list.at(rand_index)); sorted_list.erase(sorted_list.begin() + rand_index); } // Finally push back the last remaining element to the random list // The if() statement here is just a sanity check, in case K == 0 if(!sorted_list.empty()) { random_list.push_back(sorted_list.at(0)); } 

Answer 10

例如，如果要对列表进行sorting，如果要从N中提取K个元素，但不关心它们的相对顺序，则在本文中提出了一种有效的algorithm：用于连续随机采样的高效algorithm （Jeffrey Scott Vitter， ACM Transactions on Mathematical Software ，第13卷，第1期，1987年3月，第56-67页）。

使用boost来编辑以在c ++中添加代码。 我刚input，可能会有很多错误。 随机数字来自助推库，有一个愚蠢的种子，所以不要做任何严肃的事情。

 /* Sampling according to [Vitter87]. * * Bibliography * [Vitter 87] * Jeffrey Scott Vitter, * An Efficient Algorithm for Sequential Random Sampling * ACM Transactions on MAthematical Software, 13 (1), 58 (1987). */ #include <stdlib.h> #include <string.h> #include <math.h> #include <string> #include <iostream> #include <iomanip> #include <boost/random/linear_congruential.hpp> #include <boost/random/variate_generator.hpp> #include <boost/random/uniform_real.hpp> using namespace std; // This is a typedef for a random number generator. // Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand typedef boost::minstd_rand base_generator_type; // Define a random number generator and initialize it with a reproducible // seed. // (The seed is unsigned, otherwise the wrong overload may be selected // when using mt19937 as the base_generator_type.) base_generator_type generator(0xBB84u); //TODO : change the seed above ! // Defines the suitable uniform ditribution. boost::uniform_real<> uni_dist(0,1); boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist); void SequentialSamplesMethodA(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method A. { int top=NK, S, curr=0, currsample=-1; double Nreal=N, quot=1., V; while (K>=2) { V=uni(); S=0; quot=top/Nreal; while (quot > V) { S++; top--; Nreal--; quot *= top/Nreal; } currsample+=1+S; cout << curr << " : " << currsample << "\n"; Nreal--; K--;curr++; } // special case K=1 to avoid overflow S=floor(round(Nreal)*uni()); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } void SequentialSamplesMethodD(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method D. { const int negalphainv=-13; //between -20 and -7 according to [Vitter87] //optimized for an implementation in 1987 !!! int curr=0, currsample=0; int threshold=-negalphainv*K; double Kreal=K, Kinv=1./Kreal, Nreal=N; double Vprime=exp(log(uni())*Kinv); int qu1=N+1-K; double qu1real=qu1; double Kmin1inv, X, U, negSreal, y1, y2, top, bottom; int S, limit; while ((K>1)&&(threshold<N)) { Kmin1inv=1./(Kreal-1.); while(1) {//Step D2: generate X and U while(1) { X=Nreal*(1-Vprime); S=floor(X); if (S<qu1) {break;} Vprime=exp(log(uni())*Kinv); } U=uni(); negSreal=-S; //step D3: Accept ? y1=exp(log(U*Nreal/qu1real)*Kmin1inv); Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real)); if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true //step D4 Accept ? y2=0; top=Nreal-1.; if (K-1 > S) {bottom=Nreal-Kreal; limit=NS;} else {bottom=Nreal+negSreal-1.; limit=qu1;} for(int t=N-1;t>=limit;t--) {y2*=top/bottom;top--; bottom--;} if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv)) {//Accept ! Vprime=exp(log(uni())*Kmin1inv); break; } Vprime=exp(log(uni())*Kmin1inv); } // Step D5: Select the (S+1)th record currsample+=1+S; cout << curr << " : " << currsample << "\n"; curr++; N-=S+1; Nreal+=negSreal-1.; K-=1; Kreal-=1; Kinv=Kmin1inv; qu1-=S; qu1real+=negSreal; threshold+=negalphainv; } if (K>1) {SequentialSamplesMethodA(K, N);} else { S=floor(N*Vprime); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } } int main(void) { int Ntest=10000000, Ktest=Ntest/100; SequentialSamplesMethodD(Ktest,Ntest); return 0; } $ time ./sampling|tail 

在我的笔记本电脑上提供以下产品

 99990 : 9998882 99991 : 9998885 99992 : 9999021 99993 : 9999058 99994 : 9999339 99995 : 9999359 99996 : 9999411 99997 : 9999427 99998 : 9999584 99999 : 9999745 real 0m0.075s user 0m0.060s sys 0m0.000s 

Answer 11

这个Ruby代码展示了Reservoir Sampling，Algorithm R方法。 在每个循环中，我从[0,N=10)范围中selectn=5唯一的随机整数：

 t=0 m=0 N=10 n=5 s=0 distrib=Array.new(N,0) for i in 1..500000 do t=0 m=0 s=0 while m<n do u=rand() if (Nt)*u>=nm then t=t+1 else distrib[s]+=1 m=m+1 t=t+1 end #if s=s+1 end #while if (i % 100000)==0 then puts i.to_s + ". cycle..." end end #for puts "--------------" puts distrib 

输出：

 100000. cycle... 200000. cycle... 300000. cycle... 400000. cycle... 500000. cycle... -------------- 250272 249924 249628 249894 250193 250202 249647 249606 250600 250034 

0-9之间的所有整数都以几乎相同的概率被select。

这基本上是Knuth的algorithm适用于任意序列（的确，答案有这个LISP版本）。 该algorithm是O（N）在时间上，可以在内存中O（1） ，如果序列stream入它，如@ MichaelCramer的答案所示 。

Answer 12

这里有一种方法可以在O（N）中完成，无需额外存储。 我很确定这不是一个纯粹的随机分布，但它可能足够接近许多用途。

 /* generate N sorted, non-duplicate integers in [0, max[ in O(N))*/ int *generate(int n, int max) { float step,a,v=0; int i; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; for (i=0; i<n; i++) { step = (max-v)/(float)(ni); v+ = floating_pt_random_in_between(0.0, step*2.0); if ((int)v == g[i-1]){ v=(int)v+1; //avoid collisions } g[i]=v; } while (g[i]>max) { g[i]=max; //fix up overflow max=g[i--]-1; } return g; } 

Answer 13

这是Perl代码。 Grep是一个filter，和往常一样，我没有testing这个代码。

 @list = grep ($_ % I) == 0, (0..N); 

• I =间隔
• N =上限

只能通过模数运算符获得与您的间隔相匹配的数字。

 @list = grep ($_ % 3) == 0, (0..30); 

将返回0，3，6，… 30

这是伪Perl代码。 你可能需要调整它才能编译。