From: Glenn Parker <glenn.parker@...>
Date: 2005-03-23T01:05:53+09:00
Subject: Fun with method_missing

I'm afraid Pickaxe2 does not have many powerful examples for using 
method_missing.  In particular, it does not show how to use 
method_missing with a block argument, and it does not show 
method_missing actually creating the missing method.

I was able to find one example of a block arguemnt to method_missing on 
the ruby-talk list, which helped me over a bump.  I wanted to implement 
a perl-ish idiom where missing methods are defined when they are first 
referenced, so that method_missing is not needed after the first time.

The initial motivation: I was trying to write code to efficiently 
generate combinations from sets (e.g. 5 items taken 3 at a time), 
something I've needed several times.  It's a simple task, but it's easy 
to write very slow code to do it.  This is the fastest I've come up with 
so far.

For reasonably short execution times, run with arguments like "5 50" or 
"4 100".

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#!/usr/bin/ruby
# combine.rb

module Combine

   # Generate all combinations of +pick+ elements from +items+ array.
   def Combine.pick(pick, items, &block)
     pick_recurse([], pick, items.dup, &block) if pick > 0
   end

   # Automatically define new pickN methods and call them.
   def Combine.method_missing(method_id, *args, &block)
     if method_id.to_s =~ /^pick(\d+)$/
       def_pick($1.to_i).call(*args, &block)
     else
       raise NoMethodError, "invalid method Combine.#{method_id.to_s}"
     end
   end

   private

   # Iterate over combinations using recursion.
   def Combine.pick_recurse(set, pick, items, &block)
     while not items.empty?
       set.push(items.shift)
       if pick > 1
	pick_recurse(set, pick - 1, items.dup, &block)
       else
	yield set
       end
       set.pop
     end
   end

   # Define a pickN method and return the new Method object.
   def Combine.def_pick(pick)
     method_name, method_code = build_pick(pick)
     module_eval(method_code)
     method(method_name)
   end

   # Return code for pickN with recursion unrolled.
   def Combine.build_pick(pick)
     method_name = "pick#{pick}"
     method_code = [
       "def Combine.#{method_name}(items0, &block)\n",
       "set = []\n",
       (0...pick).collect do |p|
	[ "items#{p+1} = items#{p}.dup\n",
	  "while not items#{p+1}.empty?\n",
	  "set.push(items#{p+1}.shift)\n" ]
       end,
       "yield set\n",
       (0...pick).collect do |p|
	[ "set.pop\n",
	  "end\n" ]
       end,
       "end\n" ].flatten.join('')
     return method_name, method_code
   end

end

if __FILE__ == $0

   if ARGV.length != 2
     STDERR.puts "Usage: combine.rb <pick> <from>"
     exit(1)
   end

   P = ARGV[0].to_i
   F = ARGV[1].to_i

   puts "Pick 2 out of 5 (recursive):"
   Combine.pick(2, (1..5).to_a) {|set| print "#{set[0]}-#{set[1]} " }
   print "\n"

   puts "Pick 2 out of 5 (non-recursive):"
   Combine.pick2((1..5).to_a) {|set| print "#{set[0]}-#{set[1]} " }
   print "\n"

   items = (1..F).to_a
   method_id = "pick#{P}".to_sym

   require 'benchmark'

   Benchmark.bm(10) do |x|
     x.report("pick") do
       Combine.pick(P, items) do |set|
       end
     end
     x.report(method_id.to_s) do
       Combine.send(method_id, items) do |set|
       end
     end
     x.report(method_id.to_s + " (2)") do
       Combine.send(method_id, items) do |set|
       end
     end
   end

end

-- 
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>