Two Random Selections
December 10, 2010
In today’s exercise, we look at two programs that make random selections.
The first program picks an item from a list whose size is not known in advance, making a single pass through the list. The algorithm selects the first item in the list with probability 1/1, then replaces that item with the second item in the list with probability 1/2, then replaces whichever item is currently selected with the third item in the list with probability 1/3, and so on; when the end of the list is reached, each item will be selected with probability 1/n, where n is the number of items in the list. This algorithm is used in the unix fortune program, which randomly selects a line from a file of pithy sayings, and appears in the Standard Prelude under the name fortune.
The second program is used by auditors, pollsters, and others who need to randomly select m items from a population of n items. The program outputs a list of m numbers in the range 1 to n, in order; the user then selects the sampled items from a numbered list of the items in the population. The algorithm runs through the integers from 1 to n and selects each item with probability m/n, where at each step m is the number remaining to be selected and n is the number remaining in the population.
Your task is to write the two programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] 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