From: Mathieu Bouchard <matju@...>
Date: 2005-03-23T20:56:46+09:00
Subject: method_missing & combinatorics


On Wed, 23 Mar 2005, Glenn Parker wrote:
> 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.

RubyX11 0.6 (http://artengine.ca/matju/RubyX11/) has examples of both. It
does a lazy compilation of type-declarations into packers and
unpackers. However I haven't insisted on releasing it because it wasn't so
much faster, and the code still only runs in Ruby 1.6 (sorry!!!).

However most other uses of method_missing I've had, don't define new
methods, they just redirect to another one, possibly changing the args a
bit, or even, the actual job is done within the body of method_missing
(!).

> The initial motivation: I was trying to write code to efficiently 
> generate combinations from sets (e.g. 5 items taken 3 at a time), 

Take the general problem of n items taken m at a time. Represent subsets
relative to the original set together with an arbitrary enumeration of its
elements. Then each subset is an element of 0..(2**n-1). The weight of a
number is its number of "1" bits (in this context, it's also subset
cardinality). The smallest such number is always 2**m-1. Then for m=3,n=5
there are ten numbers. Here are they, sorted, followed by a list of
differences (such that the first seq is the partial sums of the second
seq).

7, 11, 13, 14, 19, 21, 22, 25, 26, 28.
  4,  2,  1,  5,  2,  1,  3,  1,  2.

If you can figure out a fast way to compute either sequence, then you have
a fast way to generate sets. If n>30 then it becomes slower because of the
use of Bignums.

Actually it's easy if you have a fast way to find the weight: then all you
have to do is, you take the previous number in the sequence (let's call it
x), find w(x+1), find out how much more weight you need by doing
k=m-w(x+1)), do x+=(1<<k), repeat until you actually get the correct
weight. Does that sound right?

in short, do x+=(1<<(m-w(x+1))) while w(x)<m.

I don't have a fast w function though. I might consider to accelerate
weight computation differentially using the identity
w(a^b)=w(a)+w(b)-2w(a&b) (which ought to be familiar from set theory
and/or probability theory). However I'm not sure it really would get any
faster...

Your version seems good. The efficiency of my bitset method doesn't expand
to sparse sets, and thus works best when m is not too far from n (say,
when m > n/32, possibly?).

What do you think of my solution?

_____________________________________________________________________
Mathieu Bouchard -=- Montr�al QC Canada -=- http://artengine.ca/matju