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.

About these ads

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 [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/12/10/programming-praxis-two-random-selections/ for a version with comments):

    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
    

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 628 other followers

%d bloggers like this: