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):
import Control.Monad import Data.List import System.Random chance :: Int -> Int -> a -> a -> IO a chance x y a b = fmap (\r -> if r < x then a else b) $ randomRIO (0, y - 1) fortune :: [a] -> IO a fortune = foldM (\a (n, x) -> chance 1 n x a) undefined . zip [1..] sample :: Int -> Int -> IO [Int] sample m n = fmap snd $ foldM (\(m', a) x -> chance m' x (m' - 1, x:a) (m', a)) (m, []) [n, n-1..1]Interesting. I did not post any code but tried to code it (I did have issues with the specification :D).
Python solution:
import random def fortune(li, remove=False): for select in enumerate(li): replace = random.randint(1,select[0]+1) if replace == 1: value = select[1] if remove: li.remove(value) return value def selectmn(m, n): allvals = [i for i in range(1,n+1)] mselected = [fortune(allvals, True) for i in range(1,m+1)] return sorted(mselected)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.
import random, itertools def rand_index(): """Yield a element chosen uniformly at random from {0}, then from {0,1}, then from {0,1,2}, ... """ for i in itertools.count(1): yield random.randrange(i) def k_of_many(iterable, k = 1): """Return a list of k items selected uniformly at random from the iterable. If the iterable yields fewer than k items, return all of them. """ result = [] for element, choice in itertools.izip(iterable, rand_index()): if len(result) < k: result.append(element) elif choice < k: result[choice] = element return result