## 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.

Pages: 1 2

[…] 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.