From: Robert Klemme <bob.news@...>
Date: 2004-05-14T17:08:53+09:00
Subject: Re: How to make combinations of an array to produce all possible expressions?


"Harry Ohlsen" <harryo@qiqsolutions.com> schrieb im Newsbeitrag
news:40A41302.9090307@qiqsolutions.com...
> Robert Klemme wrote:
>
> > Ah, similar idea but nicer coding.
>
> Coming from you, that's a much appreciated compliment!

You're welcome! :-)

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

Another good point!

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

That might be handled by an additional flag with a default value (which
one, the mathematical or the practical?).  Practically you often don't
need / want the empty set.

Funny to see how this evolves.  My current vesion looks like this:

module Enumerable
  def each_subset(skip_empty = false)
    for n in (skip_empty ? 1 : 0) ... (1 << size) do
      subset = []

      each_with_index do |elem, i|
        subset << elem if n[i]
      end

      yield subset
    end

    self
  end

  def powerset(skip_empty = false)
    subsets = []

    each_subset(skip_empty) { |s| subsets << s }

    return subsets
  end
end


Changes / Improvements:

 - self[index] is not used since it is not available with all Enumerables
 - flag 'skip_empty' added
 - self returned from iterator
 - renamed #subsets to #powerset (this is the mathematical correct term,
isn't it)
 - changed (2 << length - 1) to (1 << length)

Here's another experimental version that works even if #size is not
supported.  This really needs only #each.  Alternatively one could do an
initial iteration to calculate the size - that saves the intermediate
array.

module Enumerable
  def each_subset(skip_empty = false)
    enum = respond_to?( :size ) ? self : to_a

    for n in (skip_empty ? 1 : 0) ... (1 << enum.size) do
      subset = []

      enum.each_with_index do |elem, i|
        subset << elem if n[i] == 1
      end

      yield subset
    end

    self
  end

  def powerset(skip_empty = false)
    subsets = []

    each_subset(skip_empty) { |s| subsets << s }

    return subsets
  end
end

# test class
class Test
  include Enumerable

  def initialize(n); @n=n; end
  def each; @n.times {|c| yield c}; self; end
end

p Test.new(3).powerset


Kind regards

    robert