您如何有效地生成一个介于0和上限N之间的K个非重复整数的列表

Question

这个问题给出了所有必要的数据：在给定的间隔[0，N-1]内生成K个非重复整数序列的有效算法是什么？如果K很大并且足够接近N，那么琐碎的算法（生成随机数，然后将它们添加到序列中之前，先查找它们是否已经存在）是非常昂贵的。从链接列表中有效地选择一组随机元素提供的算法似乎比所需的更为复杂，并且需要一些实现。我刚刚找到了另一种算法，只要您知道所有相关参数，就可以很好地完成工作。

Answer 1

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

算法S（选择采样技术）。从一组N中随机选择n条记录，其中0 <n≤N。

S1。[初始化。]设置t←0，m←0。（在此算法中，m表示到目前为止选择的记录数，而t是我们处理过的输入记录的总数。）

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

S3。[测试]如果（N – t）U≥n – m，请转到步骤S5。

S4。[选择]选择样本的下一条记录，并将m和t加1。否则样本完成，算法终止。

S5。[跳过]跳过下一个记录（不包括在样本中），将t增加1，然后返回到步骤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))

Answer 2

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

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

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