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

### 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+1)
if replace == 1: value = select
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
```