An implementation of the reservoir sampling algorithm

reservoir-sample.clj

;; Todo: write as a transducer
(defn reservoir-sample
  "Uniformly choose a sample of k elements from lst"
  [k lst]
  (first
   (reduce
    (fn [[sample length] next]
      (let [r (rand-int length)]
        [(if (< r k)
           (assoc sample r next)
           sample)
         (inc length)]))
    [(vec (take k lst)) k]
    (drop k lst))))

Chooses a sample of k elements uniformly all with constant space requirements and a linear time complexity.