Programming Praxis – Two Random Selections

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.

About these ads

Tags: , , , , , , ,

3 Responses to “Programming Praxis – Two Random Selections”

  1. programmingpraxis Says:

    Please tell us about the bug.

  2. Remco Niemeijer Says:

    As usual, the code went through several iterations, so I can’t recall the exact code that produced the bug, but the basic problem was that by using ints instead of floats for the random number generation I introduced an off-by-one error because the bounds of randomRIO are inclusive, which means that asking for, say, 6 samples often produced only 4 or 5 because the final odds were 1 in 2 instead of 1 in 1.

  3. Programming Praxis – Fortune « Bonsai Code Says:

    [...] we wrote some code in a previous exercise to select a random item from a list we can just use that here [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: