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