Feature #18685
closedEnumerator.product: Cartesian product of enumerables
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 ofeach
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¶
Updated by Eregon (Benoit Daloze) over 2 years ago
- Subject changed from Enumerator.product: Cartesian product of enumerators to Enumerator.product: Cartesian product of enumerables
Updated by Eregon (Benoit Daloze) over 2 years ago
Isn't it significantly slower than doing it manually due to all these extra block and method calls etc in between?
Updated by matz (Yukihiro Matsumoto) over 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) over 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) over 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) over 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) over 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) over 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: ()
Updated by sawa (Tsuyoshi Sawada) over 2 years ago
Updated by knu (Akinori MUSHA) over 2 years ago
Updated by marcandre (Marc-Andre Lafortune) about 2 years ago
- Is duplicate of Feature #7444: Array#product_set added
Updated by hsbt (Hiroshi SHIBATA) almost 2 years ago
- Status changed from Open to Closed
https://github.com/ruby/ruby/pull/6197 has been merged for Ruby 3.2