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.

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

%d bloggers like this: