# 99 questions/Solutions/23

### From HaskellWiki

m (code formatting to shorten the lines (else scrollbars appear obscuring the text)) |
|||

Line 9: | Line 9: | ||

rnd_select l n | rnd_select l n | ||

| n<0 = error "N must be greater than zero." | | n<0 = error "N must be greater than zero." | ||

− | | otherwise = do pos <- replicateM n $ getStdRandom$randomR (0, (length l)-1) | + | | otherwise = do pos <- replicateM n $ |

+ | getStdRandom $ randomR (0, (length l)-1) | ||

return [l!!p | p <- pos] | return [l!!p | p <- pos] | ||

</haskell> | </haskell> | ||

Line 37: | Line 38: | ||

| count == (length l) = (l, gen) | | count == (length l) = (l, gen) | ||

| otherwise = rnd_select (removeAt k l) count gen' | | otherwise = rnd_select (removeAt k l) count gen' | ||

− | where (k, gen') = randomR (0, (length l) - 1) gen | + | where (k, gen') = |

+ | randomR (0, (length l) - 1) gen | ||

rnd_selectIO :: [a] -> Int -> IO [a] | rnd_selectIO :: [a] -> Int -> IO [a] | ||

Line 56: | Line 58: | ||

| otherwise = rnd_select' (removeAt k l) ((l !! k) : acc) | | otherwise = rnd_select' (removeAt k l) ((l !! k) : acc) | ||

(count - 1) gen' | (count - 1) gen' | ||

− | where (k, gen') = randomR (0, (length l) - 1) gen | + | where (k, gen') = |

+ | randomR (0, (length l) - 1) gen | ||

rnd_selectIO :: [a] -> Int -> IO [a] | rnd_selectIO :: [a] -> Int -> IO [a] |

## Revision as of 05:54, 1 June 2011

Extract a given number of randomly selected elements from a list.

import System.Random import Control.Monad (replicateM) rnd_select :: [a] -> Int -> IO [a] rnd_select [] _ = return [] rnd_select l n | n<0 = error "N must be greater than zero." | otherwise = do pos <- replicateM n $ getStdRandom $ randomR (0, (length l)-1) return [l!!p | p <- pos]

In order to use getStdRandom and randomR here, we need import module System.Random.

or using sequence all the way:

import Control.Monad (replicateM) rnd_select xs n | n < 0 = error "N must be greater than zero." | otherwise = replicateM n rand where rand = do r <- randomRIO (0, (length xs) - 1) return (xs!!r)

Alternative solution:

The original Lisp problem suggested we use our solution from problem 20. I believe that each item from the list should only appear once, whereas the above solution can reuse items.

Therefore here is an alternative which uses the "removeAt" function from problem 20:

rnd_select :: RandomGen g => [a] -> Int -> g -> ([a], g) rnd_select _ 0 gen = ([], gen) rnd_select [] _ gen = ([], gen) rnd_select l count gen | count == (length l) = (l, gen) | otherwise = rnd_select (removeAt k l) count gen' where (k, gen') = randomR (0, (length l) - 1) gen rnd_selectIO :: [a] -> Int -> IO [a] rnd_selectIO l count = getStdRandom $ rnd_select l count

If the number of items we want is the same as the number of items in the list, then we just return the list. Otherwise we remove a random item from the list and then recurse.

Another Alternative Solution:

Since the above Alternative Solution works by removing things to create the target list, it's most efficient when the target list length is > (orig list / 2). Here's another solution that's efficient in the other way (target < (orig list / 2)) by constructing an accumulator list of selected random elements. (This one also uses removeAt from problem 20)

rnd_select :: RandomGen g => [a] -> Int -> g -> ([a], g) rnd_select ol ocount ogen = rnd_select' ol [] ocount ogen where rnd_select' l acc count gen | count == 0 = (acc, gen) | otherwise = rnd_select' (removeAt k l) ((l !! k) : acc) (count - 1) gen' where (k, gen') = randomR (0, (length l) - 1) gen rnd_selectIO :: [a] -> Int -> IO [a] rnd_selectIO l count = getStdRandom $ rnd_select l count

An O(N) algorithm:

import System.Random (randomRIO) rnd_select :: [a] -> Int -> IO [a] rnd_select _ 0 = return [] rnd_select (x:xs) n = do r <- randomRIO (0, (length xs)) if r < n then do rest <- rnd_select xs (n-1) return (x : rest) else rnd_select xs n

`IO a`