Project

General

Profile

Actions

Feature #18685

closed

Enumerator.product: Cartesian product of enumerables

Added by knu (Akinori MUSHA) almost 2 years ago. Updated over 1 year ago.

Status:
Closed
Assignee:
-
Target version:
[ruby-core:108198]

Description

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


Related issues 1 (1 open0 closed)

Is duplicate of Ruby master - Feature #7444: Array#product_setOpenmatz (Yukihiro Matsumoto)Actions
Actions #1

Updated by knu (Akinori MUSHA) almost 2 years ago

  • Description updated (diff)
Actions #2

Updated by Eregon (Benoit Daloze) almost 2 years ago

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

Updated by Eregon (Benoit Daloze) almost 2 years ago

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

Actions #4

Updated by Eregon (Benoit Daloze) almost 2 years ago

  • Description updated (diff)
Actions #5

Updated by Eregon (Benoit Daloze) almost 2 years ago

  • Description updated (diff)

Updated by matz (Yukihiro Matsumoto) almost 2 years ago

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.

Updated by knu (Akinori MUSHA) almost 2 years ago

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

Updated by Eregon (Benoit Daloze) almost 2 years ago

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.

Updated by Eregon (Benoit Daloze) almost 2 years ago

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 :)

Updated by shan (Shannon Skipper) almost 2 years ago

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

Updated by knu (Akinori MUSHA) almost 2 years ago

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: ()
Actions #14

Updated by marcandre (Marc-Andre Lafortune) over 1 year ago

Updated by hsbt (Hiroshi SHIBATA) over 1 year ago

  • Status changed from Open to Closed

https://github.com/ruby/ruby/pull/6197 has been merged for Ruby 3.2

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0