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

Pages: 1 2

### 5 Responses to “Two Random Selections”

1. […] today’s Programming Praxis exercisewe have to implement two algorithms that select random items from a list […]

```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]
```
3. Interesting. I did not post any code but tried to code it (I did have issues with the specification :D).

4. Yuushi said

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)
```
5. F. Carr said

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
```