```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ``` ```; reservoir sampling (define (take n xs) (let loop ((n n) (xs xs) (ys '())) (if (or (zero? n) (null? xs)) (reverse ys) (loop (- n 1) (cdr xs) (cons (car xs) ys))))) (define (drop n xs) (let loop ((n n) (xs xs)) (if (or (zero? n) (null? xs)) xs (loop (- n 1) (cdr xs))))) (define rand ; knuth random number generator with shuffle box (let* ((a 69069) (c 1234567) (m 4294967296) (k 32) ; 32-bit ; (a 6364136223846793005) (c 1442695040888963407) ; (m 18446744073709551616) (k 256) ; 64-bit (seed (current-seconds)) (next (lambda () (set! seed (modulo (+ (* a seed) c) m)) seed)) (init (lambda (seed) (let ((box (make-vector k))) (do ((j 0 (+ j 1))) ((= j k) box) (vector-set! box j (next)))))) (box (init seed))) (lambda args (when (pair? args) (set! seed (modulo (car args) m)) (set! box (init seed))) (let* ((j (quotient (* k seed) m)) (n (vector-ref box j))) (set! seed (next)) (vector-set! box j seed) (/ n m))))) (define (randint . args) (let ((lo (if (pair? (cdr args)) (car args) 0)) (hi (if (pair? (cdr args)) (cadr args) (car args)))) (+ lo (floor (* (rand) (- hi lo)))))) (define (sample k xs) (let ((resv (list->vector (take k xs)))) (do ((xs (drop k xs) (cdr xs)) (i k (+ i 1))) ((null? xs) resv) (let ((j (randint i))) (when (< j k) (vector-set! resv j (car xs))))))) (define xs '(a b c d e f g h i j k l m n o p q r s t u v w x y z)) (display (sample 3 xs)) (newline) (display (sample 3 xs)) (newline) (display (sample 3 xs)) (newline) ```
 ```1 2 3 ``` ```#(x d q) #(a o c) #(f t o) ```