Posts Tagged ‘selection’

Programming Praxis – Two Random Selections

December 10, 2010

In today’s Programming Praxis exercise we have to implement two algorithms that select random items from a list in linear time. Let’s get started, shall we?

Some imports:

import Control.Monad
import Data.List
import System.Random

I found myself doing the same thing in both functions so I factored it out. This function gives you an x in y chance of choosing a instead of b.

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)

The first algorithm (selecting one item at random from a list) can be done by folding over the list, with each item having a decreasing chance of becoming the new choice.

fortune :: [a] -> IO a
fortune = foldM (\a (n, x) -> chance 1 n x a) undefined . zip [1..]

The second algorithm (selecting m items from a list of integers) is pretty much the same, except now we also have to keep track of how many items we selected. This version always goes through the entire list rather than stopping when m items have been selected, but since it still runs in O(n) and the resulting code is cleaner I went with this version.

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]

With random algorithms it’s always a good idea to check the distribution of the results, as was proven again today because it revealed a bug in my code.

main :: IO ()
main = do let dist n f = mapM_ (\x -> print (length x, head x)) .
                         group . sort . concat =<< replicateM n f
          dist 10000 . fmap return $ fortune ["rock", "paper", "scissors"]
          dist 10000 $ sample 6 43

The frequency distribution is pretty much equal and they sum up to the correct amount, so everything seems to be working correctly.