Two Random Selections
December 10, 2010
Here is the first algorithm. Xs
is the list from which an item is to be selected, x
is the selected item, and n
counts the items in the list:
(define (fortune xs)
(let loop ((n 1) (x #f) (xs xs))
(cond ((null? xs) x)
((< (rand) (/ n))
(loop (+ n 1) (car xs) (cdr xs)))
(else (loop (+ n 1) x (cdr xs))))))
Here is the second algorithm. N
is decremented at each step, m
is decremented whenever the current item is selected, and the current item x
increases at each step:
(define (sample m n)
(let loop ((m m) (n n) (x 1) (xs '()))
(cond ((zero? n) (reverse xs))
((< (rand) (/ m n))
(loop (- m 1) (- n 1) (+ x 1) (cons x xs)))
(else (loop m (- n 1) (+ x 1) xs)))))
Here are the functions in action; if you're lucky, fortune
can give you the winning throw in a competitive game of rock-paper-scissors, and sample
can give you the winning numbers in tomorrow’s lottery:
> (fortune '(rock paper scissors))
scissors
> (sample 6 43)
(2 13 14 17 20 26)
We used rand
from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/6raHapY0.
[…] today’s Programming Praxis exercisewe have to implement two algorithms that select random items from a list […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/10/programming-praxis-two-random-selections/ for a version with comments):
Interesting. I did not post any code but tried to code it (I did have issues with the specification :D).
Python solution:
Consider “k_of_many”, which takes a subset of k elements uniformly at random from a list of unknown size. (Or all the elements, if the list is shorter than k.) Then “fortune” and “sample” are special cases.