TA貢獻1821條經(jīng)驗 獲得超5個贊
在Knuth 的《計算機編程藝術，第二卷：第二數(shù)值算法》第三版中，描述了以下選擇采樣算法：
算法S（選擇采樣技術）。從一組N中隨機選擇n條記錄，其中0 <n≤N。
S1。[初始化。]設置t←0，m←0。（在此算法中，m表示到目前為止選擇的記錄數(shù)，而t是我們處理過的輸入記錄的總數(shù)。）
S2。[Generate U.]生成一個隨機數(shù)U，均勻分布在零和一之間。
S3。[測試]如果（N – t）U≥n – m，請轉到步驟S5。
S4。[選擇]選擇樣本的下一條記錄，并將m和t加1。否則樣本完成，算法終止。
S5。[跳過]跳過下一個記錄（不包括在樣本中），將t增加1，然后返回到步驟S2。
與描述相比，實現(xiàn)可能更容易遵循。這是一個從列表中選擇n個隨機成員的Common Lisp實現(xià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))))
這是一個不使用遞歸的實現(xiàn)，并且可以用于所有類型的序列：
(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))
TA貢獻1815條經(jīng)驗 獲得超10個贊
實際上，可以在空間中執(zhí)行此操作，而與選擇的元素數(shù)量成正比，而不是與要選擇的集合的大小成正比，而與所選擇的總集合的比例無關。您可以通過生成隨機排列來執(zhí)行此操作，然后從中進行選擇，如下所示：
選擇一個分組密碼，例如TEA或XTEA。使用XOR折疊可將塊大小減小到比從中選擇的集合大2的最小冪。使用隨機種子作為密碼的密鑰。要在置換中生成元素n，請使用密碼對n進行加密。如果輸出號碼不在您的設置中，請對其進行加密。重復直到數(shù)字在集合內。平均而言，每個生成的號碼您必須進行少于兩次的加密。這樣做還有一個好處，就是如果您的種子是加密安全的，那么整個排列也是安全的。
我在這里詳細介紹了這一點。
舉報