笛卡尔积红宝石

Question

class CartesianProduct
include Enumerable
# your code here
end
#Examples of use
c = CartesianProduct.new([:a,:b], [4,5])
c.each { |elt| puts elt.inspect }
# [:a, 4]
# [:a, 5]
# [:b, 4]
# [:b, 5]
c = CartesianProduct.new([:a,:b], [])
c.each { |elt| puts elt.inspect }
# (nothing printed since Cartesian product
# of anything with an empty collection is empty)

我是红宝石的新手.我理解如何定义笛卡儿积的实例方法,但我对此毫无头绪.我应该如何构造类对象以满足要求.

Answer 1

我建议使用Array#product.

[:a, :b].product [4,5]

这将产生您想要的输出.

irb(main):001:0> [:a, :b].product [4,5]
=> [[:a, 4], [:a, 5], [:b, 4], [:b, 5]]
irb(main):002:0> 

如果你想要一个惰性的排列生成器,我之前写过这样的东西.但我警告你,如果你有大量的排列来计算它可能需要一段时间.你应该能够从这个文件的前40-45行获取你需要的东西(这个文件无论如何都是一个实验).

诀窍是使用Ruby 1.9.2构建枚举器,以便通过数组数组工作.因此,您首先构建一个无限循环遍历数组的枚举器,并在数组数组枚举器中跟踪第一个输出集,并在第二次触发时结束循环.这是我弄清楚如何终止这种循环的唯一方法.

def infinite_iterator(array)
  Enumerator.new do |result|
    loop do
      array.cycle { |item| result << item }
    end
  end
end

def cartesian_iterator(data)
  Enumerator.new do |result|
    first = data.map { |p| p.next }
    result << first

    i = 1
    parts = first.dup
    loop do
      parts[2-i] = data[2-i].next
      break if parts == first

      result << parts.join
      i = ((i + 1) % parts.size)
    end
  end
end

array = [ infinite_iterator([:a,:b]), infinite_iterator([4,5]) ]
generator = cartesian_iterator(array)

generator.each { |a| p a }

Answer 2

您需要each在类中定义一个方法,该方法需要调用产品yield的每个组合.

你可以使用Array#product,但它返回一个数组,所以它不是懒惰的.

在Ruby 2.0中有一个提议Array.product可以做到这一点.

Answer 3

我不会使用一个类,但保持问题的结构,我写道:

class CartesianProduct
  include Enumerable

  def initialize(xs, ys)
    @xs = xs
    @ys = ys
  end

  def each
    return to_enum unless block_given?
    @xs.each do |x| 
      @ys.each { |y| yield [x, y] }
    end
  end
end

相反,如果懒惰很重要,我只会编写xs.product(ys)或构建自己的Array#lazy_product(参见此票).