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

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

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

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

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

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

“计算机编程的艺术”第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)) 

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

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

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

下面的代码(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?

生成一个数组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卷中描述

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

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

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

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

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

油藏采样版本非常简单:

 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。

我的解决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)); } 

例如,如果要对列表进行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 

这个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的答案所示 。

这里有一种方法可以在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; } 

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

 @list = grep ($_ % I) == 0, (0..N); 
  • I =间隔
  • N =上限

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

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

将返回0,3,6,… 30

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