From: Harry Ohlsen <harryo@...>
Date: 2004-05-14T09:30:02+09:00
Subject: Re: How to make combinations of an array to produce all possible expressions?

Robert Klemme wrote:

> Ah, similar idea but nicer coding.

Coming from you, that's a much appreciated compliment!

> I like especially your calculation of
> the counting range and int[idx] as bit test.  I didn't know that one.

I discovered during a re-browse of pickaxe a couple of months ago, but this is the first time I've actually had a chance to use it.
 
> Btw, you don't need the test for length 0 if you do
> 
> for n in 1 ... (2<<length) do

Good point.

Something I was thinking about was that the power set (set of subsets) becomes large very quickly (obvious from the "2 << length", I guess).  It might be nice to have an iterator, too.  The method that returns the collection of subsets could then just use it.

Something like this (I've removed the empty set test, since I think this is cleaner in a mathematical sense) ...

module Enumerable
  def each_subset(&block)
    (2 << length - 1).times do |n|
      subset = []

      length.times do |i|
        if n[i] == 1
          subset << self[i]
        end
      end

      yield subset
    end
  end

  def subsets
    subsets = []

    each_subset { |s| subsets << s }

    return subsets
  end
end

if __FILE__ == $0

  conds = ["@title='Foo'", "@edition='Bar'", "@date='20040513'"]

  puts "Using iterator ..."
  puts

  conds.each_subset { |subset| p subset.join(" and ") }

  puts
  puts "Using aggregate ..."
  puts

  conds.subsets.collect { |subset| p subset.join(" and ") }

end