From: "Kroeger Simon (ext)" <simon.kroeger.ext@...>
Date: 2005-08-01T21:58:08+09:00
Subject: [QUIZ] a very late SOLUTION

Hi all,

I know I'm too late, but reading through the past quizes, I came across
http://www.rubyquiz.com/quiz39.html and had an idea i couldn't spot in
the
summary. As there is no quiz this week, perhaps someone has some time to
spare and would like to share his/her thoughts with me.

----------------------------------------------------------
def sample members, lower, upper
    $size = upper - lower
    if $size == members
        (lower...upper).each {|i| puts i}
        return
    end
    $range = $size / 2
    distribution = ($range < members) ? $range - rand($size - members +
1) : rand(members+1)
    
    sample(distribution, lower, lower + $range) if distribution > 0 
    sample(members-distribution, lower + ((upper-lower) / 2), upper) if
members-distribution > 0
end

sample(ARGV[0].to_i, 0, ARGV[1].to_i)
----------------------------------------------------------

As one can easily see this is an recursive approach, the range is split 
in half each recursion and it is randomly choosen how many of the
reminding
members are in each of the two halfes. This is nearly as fast as the
hash approach and doesn't need a sort and even eats up a lot less
memory.

What I'm not sure about is if the members are spread evenly - is there
some theoretician that can help me?

Simon