这个问题给出了所有必要的数据：在给定的时间间隔[0，N-1]内生成K个非重复整数序列的有效算法是什么。如果K很大并且足够接近N，那么琐碎的算法(生成随机数并在将它们添加到序列中之前先查找它们以查看它们是否已经存在)非常昂贵。

从链接列表中有效地选择一组随机元素中提供的算法似乎比必需的更为复杂，并且需要一些实现。只要我们知道所有相关参数，我就找到了另一种似乎可以很好地完成工作的算法。

解决方案

通过将K号存储在哈希存储中来加快平凡的算法。在开始之前了解K可以消除插入哈希表的所有效率低下的问题，并且我们仍然可以获得快速查找的好处。

以下代码(在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;
 }

有谁知道我在哪里可以找到更多像这样的宝石？

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

然后将前K个项目混洗。

改组：

• 开始J = N-1
• 选择一个随机数0 ... J(例如R)
• 从" J"中减去" 1"并重复。

最后，取K个最后一个元素。

这实际上是从列表中选择一个随机元素，将其移出，然后从其余列表中选择一个随机元素，依此类推。

需要O(K)和O(N)的时间工作，需要O(N)的存储。

改组部分称为Fisher-Yates改组或者Knuth的改组，在《计算机编程的艺术》第二卷中有介绍。

这是Perl代码。 Grep是一个过滤器，和往常一样，我没有测试此代码。

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

• I =间隔
• N =上限

仅通过模运算符获得与间隔匹配的数字。

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

将返回0、3、6，... 30

这是伪Perl代码。我们可能需要对其进行调整才能进行编译。

Python库中的random模块使它极其简单和有效：

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

样本函数返回从给定序列中选择的K个唯一元素的列表。
xrange是一个"列表仿真器"，即它的行为就像一个连续数字的列表，而没有在内存中创建它，这使得它非常快地完成像这样的任务。

水库采样版本非常简单：

my $N = 20;
my $k;
my @r;

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

print @r;

这是STDIN中随机选择的$ N行。如果我们不使用文件中的行，则用其他内容替换<> / $ _东西，但这是一个非常简单的算法。

这是一种无需额外存储即可在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)(n-i);
        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;
 }

我的解决方案是面向C ++的，但是我敢肯定它可以转换为其他语言，因为它非常简单。

• 首先，生成包含K个元素(从0到K)的链表
• 然后，只要列表不为空，就生成一个介于0和向量大小之间的随机数
• 将该元素放入另一个向量中，然后将其从原始列表中删除

该解决方案仅涉及两次循环迭代，并且不涉及哈希表查找或者类似的任何操作。因此，在实际代码中：

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

实际上，可以在空间中执行此操作，而与选择的元素数量成正比，而不是与要选择的集合的大小成正比，无论我们要选择的集合占总集合的比例是多少。我们可以通过生成随机排列来执行此操作，然后从中进行选择，如下所示：

选择一个分组密码，例如TEA或者XTEA。使用XOR折叠可将块大小减小到比从中选择的集合大2的最小幂。使用随机种子作为密码的密钥。要在置换中生成元素n，请使用密码对n进行加密。如果输出编号不在设置中，请对其进行加密。重复直到数字在集合内。平均而言，每个生成的号码我们必须进行少于两次的加密。这样做还有一个好处，就是如果种子是加密安全的，那么整个排列也是安全的。

我在这里详细介绍了这一点。

Knuth在《计算机编程艺术》，第2卷：《半数值算法》，第三版中描述了以下选择采样算法：

Algorithm S (Selection sampling technique). To select n records at random from a set of N, where 0 < n ≤ N.
  
  S1. [Initialize.] Set t ← 0, m ← 0. (During this algorithm, m represents the number of records selected so far, and t is the total number of input records that we have dealt with.)
  
  S2. [Generate U.] Generate a random number U, uniformly distributed between zero and one.
  
  S3. [Test.] If (N – t)U ≥ n – m, go to step S5.
  
  S4. [Select.] Select the next record for the sample, and increase m and t by 1. If m < n, go to step S2; otherwise the sample is complete and the algorithm terminates.
  
  S5. [Skip.] Skip the next record (do not include it in the sample), increase t by 1, and go back to step S2.

与描述相比，实现可能更容易遵循。这是一个从列表中选择n个随机成员的Common Lisp实现：

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

这是一个不使用递归的实现，并且可以用于所有类型的序列：

(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) 
                   (- n m))
            (setf (elt result m) (elt sequence i))
            (incf m))
       until (= m n))
    result))

例如，如果列表已排序，则要从N个元素中提取K个元素，但不关心它们的相对顺序，则在《序列随机抽样的有效算法》(Jeffrey Scott Vitter， ACM Transactions on Mathematical Software，第13卷，第1期，1987年3月，第56-67页)。

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

/* 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=N-K, 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=N-S;}
            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

步骤1：生成整数列表。
步骤2：执行Knuth随机播放。

请注意，我们不需要对整个列表进行混洗，因为Knuth Shuffle算法仅允许我们应用n次混洗，其中n是要返回的元素数。生成列表仍然会花费与列表大小成比例的时间，但是我们可以将现有列表重用以满足将来的任何改组需求(假设大小保持不变)，而无需在重新启动改组算法之前预先对部分改组的列表进行重新排序。

Knuth Shuffle的基本算法是从整数列表开始。然后，将第一个整数与列表中的任何数字交换，然后返回当前(新)的第一个整数。然后，将第二个整数与列表中的任何数字(第一个除外)交换，并返回当前(新的)第二个整数。然后...等等...

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