Project

General

Profile

Actions

Feature #18685

closed

Enumerator.product: Cartesian product of enumerables

Added by knu (Akinori MUSHA) 10 months ago. Updated 2 months ago.

Status:
Closed
Priority:
Normal
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) 10 months ago

  • Description updated (diff)
Actions #2

Updated by Eregon (Benoit Daloze) 10 months ago

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

Updated by Eregon (Benoit Daloze) 10 months 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) 10 months ago

  • Description updated (diff)
Actions #5

Updated by Eregon (Benoit Daloze) 10 months ago

  • Description updated (diff)

Updated by matz (Yukihiro Matsumoto) 9 months 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) 9 months 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) 9 months 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) 9 months 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) 9 months 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) 9 months 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) 5 months ago

Updated by hsbt (Hiroshi SHIBATA) 2 months 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