Feature #18685: Enumerator.product: Cartesian product of enumerables

• Status: Open
• Priority: Normal
• Assignee: -
• Target version: 3.2

[knu (Akinori MUSHA)]

I'd like to add a new Enumerator class method for generating the Cartesian product of given enumerators.
A product here does not mean an accumulated array of arrays, but an enumerator to enumerate all combinations.

product = Enumerator.product(1..3, ["A", "B"])
p product.class #=> Enumerator

product.each do |i, c|
  puts "#{i}-#{c}"
end

=begin output
1-A
1-B
2-A
2-B
3-A
3-B
=end

This can be used to reduce nested blocks and allows for iterating over an indefinite number of enumerable objects.

Implementation notes

• It should internally use each_entry instead of each on enumerable objects to make sure to capture all yielded arguments.

• If no enumerable object is given, the block is called once with no argument.

• It should reject a keyword-style hash argument so we can add keyword arguments in the future without breaking existing code.

• Here's an example implementation:

  # call-seq:
  #   Enumerator.product(*enums)                   -> enum
  #   Enumerator.product(*enums) { |*args| block } -> return value of args[0].each_entry {}
  def Enumerator.product(*enums, **nil, &block)
   # TODO: size should be calculated if possible
    return to_enum(__method__, *enums) if block.nil?
  
    enums.reverse.reduce(block) { |inner, enum|
      ->(*values) {
        enum.each_entry { |value|
          inner.call(*values, value)
        }
      }
    }.call()
  end
  

• Not to be confused with Enumerator.produce. 😝

Prior case

• Python: https://docs.python.org/3/library/itertools.html#itertools.product

[knu (Akinori MUSHA)]

• Description updated (diff)

[Eregon (Benoit Daloze)]

• Subject changed from Enumerator.product: Cartesian product of enumerators to Enumerator.product: Cartesian product of enumerables

[Eregon (Benoit Daloze)]

Isn't it significantly slower than doing it manually due to all these extra block and method calls etc in between?

[Eregon (Benoit Daloze)]

• Description updated (diff)

[Eregon (Benoit Daloze)]

• Description updated (diff)

[matz (Yukihiro Matsumoto)]

Looping class method is an unusual pattern in Enumerable. So I first hesitated, but actually it's the only way to go if we want to introduce `product'.
And the method seems to be convenient. Thus, I accept.
@Eregon (Benoit Daloze) If the performance matters, we can re-implement it in C.

Matz.

[knu (Akinori MUSHA)]

Thanks. Performance monsters can also special-case arrays and ranges and omit calls to each_entry to boost performance. 😂

[Eregon (Benoit Daloze)]

My performance concern was not about Ruby vs C, writing in C would have the same issues.

What I'm saying is this:

(1..3).each do |i|
  ["A", "B"].each do |c|
    puts "#{i}-#{c}"
  end
end

will always be faster than:

Enumerator.product(1..3, ["A", "B"]).each do |i, c|
  puts "#{i}-#{c}"
end

because the second has a generic/cannot-do-sensible-inline-cache loop and lots of array allocation and splatting.

So Enumerator.product makes sense when one doesn't know how many enums to combine, or a large number of them, but for 2-3 it's better performance-wise (and maybe also for clarity) to just use nested each.

[Eregon (Benoit Daloze)]

And between writing Enumerator.product in Ruby or C I'd prefer a lot in Ruby because it's a million times more readable, and it can be reused by other Ruby implementations :)

[shan (Shannon Skipper)]

It might also be nice to require at least one enum argument, since Enumerator.product #=> [nil] seems a bit odd. Here's a stab at lazy size:

def Enumerator.product(*enums, **nil, &block)
  raise ArgumentError, 'wrong number of arguments (given 0, expected 1..)' if enums.empty?

  unless block_given?
    return to_enum(__method__, *enums) do
      enums.reduce(1) do |acc, enum|
        enum_size = enum.size
        break unless enum_size

        acc * enum_size
      end
    end
  end

  enums.reverse.reduce(block) do |inner, enum|
    lambda do |*values|
      enum.each_entry do |value|
        inner.call(*values, value)
      end
    end
  end.call
end

[knu (Akinori MUSHA)]

That's actually not a mathematical idea. The 0-ary Cartesian product of sets should be defined as a singleton set for theoretical and practical reasons. It's just like 2^0 equals to 1.

Python's itertools.product aligns with this theory.

import itertools

for i in itertools.product(range(3), range(3)):
  print("2-ary: " + repr(i))

for i in itertools.product(range(3)):
  print("1-ary: " + repr(i))

for i in itertools.product():
  print("0-ary: " + repr(i))

Output:

2-ary: (0, 0)
2-ary: (0, 1)
2-ary: (0, 2)
2-ary: (1, 0)
2-ary: (1, 1)
2-ary: (1, 2)
2-ary: (2, 0)
2-ary: (2, 1)
2-ary: (2, 2)
1-ary: (0,)
1-ary: (1,)
1-ary: (2,)
0-ary: ()

[sawa (Tsuyoshi Sawada)]

Related to #6499 #7444 #8970