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

Question

该问题给出了所有必要的数据:在给定区间[0,N-1]内生成一系列K个非重复整数的有效算法是什么.平凡算法(产生随机数,并把它们添加到序列,看着他们,看看他们是否已经在那里之前)是非常昂贵的,如果ķ大且足够接近ñ.

在从链表中有效地选择一组随机元素中提供的算法似乎比必要的更复杂,并且需要一些实现.我刚刚发现了另一种似乎可以完成工作的算法,只要您知道所有相关参数,只需一次通过即可.

Answer 1

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

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

samplefunction返回从给定序列中选择的K个唯一元素的列表.
xrange是一个"列表模拟器",即它的行为类似于连续数字的列表而不在内存中创建它,这使得它对于像这样的任务来说超级快.

Answer 2

在计算机编程的艺术,第2卷:研究数学算法,第三版,Knuth描述了以下选择抽样算法:

算法S(选择抽样技术).从一组N中随机选择n个记录,其中0 <n≤N.

S1.[初始化.]设置t←0,m←0.(在此算法中,m表示到目前为止选择的记录数,t是我们处理的输入记录总数.)

S2.[Generate U.]生成随机数U,均匀分布在0和1之间.

S3.[测试.]如果(N-t)U≥n-m,转到步骤S5.

S4.[选择.]选择样本的下一条记录,并将m和t增加1.如果m <n,转到步骤S2; 否则样本完成,算法终止.

S5.[跳过.]跳过下一条记录(不要将其包含在样本中),将t增加1,然后返回步骤S2.

实施可能比描述更容易遵循.这是一个Common Lisp实现,从列表中选择n个随机成员:

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

实际上,可以在与所选元素数量成比例的空间中执行此操作,而不是您选择的集合的大小,而不管您选择的总集合的比例是多少.你通过生成一个随机排列,然后从中选择如下:

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

我在这里更详细地写了这篇文章.