From: Trans <transfire@...>
Date: 2007-01-31T20:25:08+09:00
Subject: Re: cartesian product of arrays

On Jan 30, 11:07 am, "diam" <d...@ensta.fr> wrote:
> > understood. actually i have a VERY fast implementation already that
> > was written by Michael Neuman. to be so fast it's very ugly though :-)
> > want to see?
>
> Yes please,
> The API and the efficiency are both important for a potential standard
> library,
> (so the name should be carefully choosen !)
> -- Maurice

Here ya go....


require 'generator'

module Enumerable

  class << self

    # Provides the cross-product of two or more Enumerables.
    # This is the class-level method. The instance method
    # calls on this.
    #
    #   Enumerable.cross([1,2], [4], ["apple", "banana"])
    #   #=> [[1, 4, "apple"], [1, 4, "banana"], [2, 4, "apple"], [2,
4, "banana"]]
    #
    #   Enumerable.cross([1,2], [3,4])
    #   #=> [[1, 3], [1, 4], [2, 3], [2, 4]]
    #
    #--
    # TODO Make a more efficient version just for Array (?)
    #++

    def cartesian_product(*enums, &block)
      raise if enums.empty?
      gens = enums.map{|e| Generator.new(e)}
      return [] if gens.any? {|g| g.end?}

      sz = gens.size
      res = []
      tuple = Array.new(sz)

      loop do
        # fill tuple
        (0 ... sz).each { |i|
          tuple[i] = gens[i].current
        }
        if block.nil?
          res << tuple.dup
        else
          block.call(tuple.dup)
        end

        # step forward
        gens[-1].next
        (sz-1).downto(0) do |i|
          if gens[i].end?
            if i > 0
              gens[i].rewind
              gens[i-1].next
            else
              return res
            end
          end
        end
      end #loop
    end

    alias :cart, :cartesian_product
  end


  # The instance level version of <tt>Enumerable::cartesian_product</
tt>.
  #
  #   a = []
  #   [1,2].cart([4,5]){|elem| a << elem }
  #   a  #=> [[1, 4],[1, 5],[2, 4],[2, 5]]
  #
  #--
  # TODO Make a more efficient version just for Array (?)
  #++

  def cart(*enums, &block)
    Enumerable.cart(self, *enums, &block)
  end

  alias :cart, :cartesian_product
end