From: Glenn Parker <glenn.parker@...>
Date: 2005-03-23T23:50:47+09:00
Subject: Re: method_missing & combinatorics

Mathieu Bouchard wrote:
> 
> 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
> (!).

If you run the benchmark I posted, you should note that the speedup 
between the first and second tests is fairly small, while the difference 
between the first two tests and the third one is significant.  The first 
test generates and evals a non-recursive method, then calls it.  The 
second test just calls the method created during the first test.  The 
third test calls a recursive version of the same algorithm.

The overhead of generating and evaling (in this case) is small, but the 
difference between non-recursive and recursive methods is big.  So, I 
suppose what I _could_ do is generate and eval code to find the result 
without actually adding a new method to the module.  But I still like 
the trick of defining new methods on demand.

>>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.

I also thought of enumerating through bit-patterns looking for those 
with the desired number of 1-bits.  Bits in a byte can be counted using 
a lookup table with 2**8 entries.  Then you sum up the bits for each 
byte in an integer.

> 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.

Yup, this idea runs into problems when applied to big domains, i.e. long 
bit arrays.  Arbitrary length bit arrays would be a useful extension for 
Ruby.

Then there's the problem of using each bit pattern result to produce a 
usable collection of items.

An aside: it's funny how Ruby supports Fixnum#[], but not Fixnum#[]=. 
Another asymmetry arising from immutable Fixnum objects, I suppose.  I 
would deprecate Fixnum#[], replacing it with Fixnum#bit_test and 
Fixnum#bit_assign.

> 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?

Not fair... still morning... brain is cold.

Even if it is correct, it doesn't sound like it will produce a result 
any faster (on average) than just iterating and testing w.

> 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?

I think you should try coding it up and see what happens.  :)

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