From: James Edward Gray II <james@...>
Date: 2005-07-19T00:51:32+09:00
Subject: Re: [SOLUTION] Sampling (#39)

On Jul 17, 2005, at 6:05 PM, Dominik Bathon wrote:



> I have wondered about this, since I first read this week's quiz:  
> Did your solution really need half an hour? What is it doing that  
> long?
>
>

Yes, mine really took half an hour.  I assume it spent the time  
counting to 1_000_000_000.  Here's the code:

#!/usr/local/bin/ruby

usage = <<END_USAGE
Usage:  #{File.basename(__FILE__)} MEMBERS LIMIT

MEMBERS:  The number of members you want in the sample.  (Integer)
   LIMIT:  The upper limit for the sample range.  All     (Integer)
           members will between 0 and LIMIT - 1.

Note that MEMBERS must be less than LIMIT.
END_USAGE

unless ARGV.size == 2 and ARGV.all? { |num| num =~ /^[\d_]+$/ }
     puts usage
     exit
end

members, limit = ARGV.map { |num| Integer(num) }

unless members < limit
     puts usage
     exit
end

0.upto(limit - 1) do |num|
     if rand(limit) % (limit - num) < members
         puts num
         members -= 1
     end
end

__END__



>> Not really picking on you Dominik.  Just showing that there are  
>> other problems in this challenge besides the one I initially posted.
>>
>>
>>
>
> Yes, I (and most of the others) didn't handle that special case. As  
> Joost Diepenmaat said in his reply to Bill Kelly's solution:
>
> As soon as samples.size > total.size / 2 it's trivial to turn the
> algorithm on its head (i.e. randomly select items that you'll skip,
> then loop through the set and print all items that aren't selected).
>
>

See my reply to that message.

James Edward Gray II