The Kitchen Sink and Other Oddities

Atabey Kaygun

Knut’s Algorithm-S in Common Lisp

Description of the problem

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

This 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!