Knut’s Algorithm S is an algorithm for taking \(k\) samples uniformly randomly from a list. At Rosetta Code there is a Common Lisp implementation, but I wrote my own.
(defun sampler (k)
(let ((i 0)
(res nil))
(lambda (x)
(progn
(cond ((null x) res)
((> k i) (push x res))
((> k (random i)) (setf (elt res (random k)) x)))
(incf i)
(reverse res)))))SAMPLERThis function for a sample size \(k\) returns a function. Each time one calls this function with an item, we get a pool of objects of size \(k\). At the end of calling this function \(N\)-times, the pool contains samples chosen uniformly randomly from the collective list of objects fed into the function.
Let us test if the sampling is uniformly random:
(let ((res (make-list 10 :initial-element 0))
(pool (loop for i from 0 below 10 collect i)))
(dotimes (i 10000 res)
(let ((s (sampler 3)))
(loop repeat 100 do (loop for x in pool do (funcall s x)))
(loop for y in (funcall s nil) do
(incf (elt res y))))))(2944 2928 3011 2971 3144 2912 2996 3040 2985 3069)Yes, it is!