Project

General

Profile

Actions

Feature #18685

closed

Enumerator.product: Cartesian product of enumerables

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

Added by knu (Akinori MUSHA) over 3 years ago. Updated almost 3 years 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 2 (2 open0 closed)

Updated by knu (Akinori MUSHA) over 3 years ago Actions #1

  • Description updated (diff)

Updated by Eregon (Benoit Daloze) over 3 years ago Actions #2

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

Updated by Eregon (Benoit Daloze) over 3 years ago Actions #3 [ruby-core:108199]

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

Updated by Eregon (Benoit Daloze) over 3 years ago Actions #4

  • Description updated (diff)

Updated by Eregon (Benoit Daloze) over 3 years ago Actions #5

  • Description updated (diff)

Updated by matz (Yukihiro Matsumoto) over 3 years ago Actions #6 [ruby-core:108334]

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) over 3 years ago Actions #7 [ruby-core:108335]

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

Updated by Eregon (Benoit Daloze) over 3 years ago Actions #8 [ruby-core:108346]

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) over 3 years ago Actions #9 [ruby-core:108347]

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) over 3 years ago Actions #10 [ruby-core:108387]

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) over 3 years ago Actions #11 [ruby-core:108388]

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

Updated by marcandre (Marc-Andre Lafortune) about 3 years ago Actions #14

Updated by hsbt (Hiroshi SHIBATA) almost 3 years ago Actions #15 [ruby-core:110790]

  • Status changed from Open to Closed

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

Updated by nobu (Nobuyoshi Nakada) 10 months ago Actions #16

  • Related to Bug #21089: Missing methods on enumerators created from Enumerator::product and Enumerator::Chain added
Actions

Also available in: PDF Atom