Cartesian product - next to last version

ruby-talk
1

Hello,

Since the original thread got a little long, I decided to post my next to
last version in a new thread. My previous version gave results like
[[1,4],7] for more than two arrays when you really wanted [1,4,7]. The trick
is to flatten each element of the product. The following works for any
number of arrays. Of course you might want a product in which the elements
of that product are arrays. Any suggestions?

class Array

  def cartprod(b=[])
    if b.empty? then
      #assume self an array of arrays
      inject {|cp,x| cp.cartprod(x) }
    else
      z = inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
      z.collect! {|x| x.flatten }
    end
  end

end

a=[1,2,3]
b=[4,5,6]
c=[7,8,9]

# works fine
p [a,b,c].cartprod

# doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
d=[10, [11,12]]
p [a,b,c,d].cartprod

2

Here is my stab at the problem (I made it as a standalone method, as I
don't think of this operation as something that an array can do:

require 'test/unit'

def cartprod(base, *others)
  return base.map{|a| [a] } if others.empty?
  others = cartprod(*others)
  base.inject() { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
end

class CarprodTest < Test::Unit::TestCase
  def test_simple
    assert_equal([[1, 'a'], [1, 'b'],
      [2, 'a'], [2, 'b'],
      [3, 'a'], [3, 'b']],
     cartprod([1,2,3], %w(a b)),
                 'Simple Cartesian Product failed')
    assert_equal([[1, "a"], [1, "b"], [1, "c"],
                  [2, "a"], [2, "b"], [2, "c"],
      [3, "a"], [3, "b"], [3, "c"]],
     cartprod(1..3, 'a'..'c'),
                 'Simple Cartesian Product with ranges failed')
  end
  
  def test_multiple
    assert_equal([[1, 'a', :A], [1, 'a', :B], [1, 'b', :A], [1, 'b', :B],
      [2, 'a', :A], [2, 'a', :B], [2, 'b', :A], [2, 'b', :B]],
     cartprod([1,2], %w(a b), [:A, :B]),
                 'Multiple Cartesian Product failed')
  end

  def test_array
    assert_equal([[1, ["a", "a"]], [1, ["b", "b"]],
                  [2, ["a", "a"]], [2, ["b", "b"]],
      [3, ["a", "a"]], [3, ["b", "b"]]],
                 cartprod(1..3, [%w(a a), %w(b b)]),
     'Cartesian Product with arrays failed')
  end

  def test_base_cases
    assert_equal(, cartprod(), "Base case empty array is not correct")
    assert_equal([[1], [2], [3]], cartprod(1..3), "Base case single
array is not correct")
  end
end

regards,

Brian

···

On 11/08/05, walter a kehowski <wkehowski@cox.net> wrote:

Hello,

Since the original thread got a little long, I decided to post my next to
last version in a new thread. My previous version gave results like
[[1,4],7] for more than two arrays when you really wanted [1,4,7]. The trick
is to flatten each element of the product. The following works for any
number of arrays. Of course you might want a product in which the elements
of that product are arrays. Any suggestions?

class Array

  def cartprod(b=)
    if b.empty? then
      #assume self an array of arrays
      inject {|cp,x| cp.cartprod(x) }
    else
      z = inject() {|a,x| b.inject(a) {|a,y| a << [x,y]}}
      z.collect! {|x| x.flatten }
    end
  end

end

a=[1,2,3]
b=[4,5,6]
c=[7,8,9]

# works fine
p [a,b,c].cartprod

# doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
d=[10, [11,12]]
p [a,b,c,d].cartprod

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

3

In such cases, I use the Vector class (require 'matrix') as the 'atomic' unit. Then Array#flatten doesn't peek inside the Vectors and flatten them inappropriately.

···

On Aug 11, 2005, at 5:06 AM, walter a kehowski wrote:

Of course you might want a product in which the elements
of that product are arrays. Any suggestions?

4

In such cases, I use the Vector class (require 'matrix') as the
'atomic' unit. Then Array#flatten doesn't peek inside the Vectors and
flatten them inappropriately.

require 'matrix'
# see page 694 of PR

···

#

class Array

  def cartprod(b=)

    if b.empty? then
      #assume self an array of arrays
      z=inject {|cp,x| cp.cartprod(x) }
    else
      z = inject() {|a,x| b.inject(a) {|a,y| a << [x,y]}}
      z.collect! {|x| x.flatten }
    end
  end

end

#Everything works
a=[1,2]
b=[4,5]
c=[7,8]
p [a,b,c].cartprod

d=[10, Vector[11,12]]
p [a,b,c,d].cartprod

5

Brian Schröder offered:

def cartprod(base, *others)
  return base.map{|a| [a] } if others.empty?
  others = cartprod(*others)
  base.inject() { | r, a | others.inject(r) { | r, b | r << ([a,
*b]) } }
end

Wow - that's nice and functional!

My procedural solution is much uglier, but it 1) isn't recursive and 2)
yields results to a given block as it iterates.

If given a block, the following will return nil, but pass the values into a
given block:

a=[[1,2,3],[4,5,6],[7,8,9]]
a.cartprod do |a0e, a1e, a2e|
  # ...
end

class Array
  def cartprod

    unless block_given?
      ret =
      cartprod {|tuple| ret << tuple}
      return ret
    end
    return if any? {|a| a.size == 0 }
    index = [0] * size
    begin
      yield *zip(index).map {|a| a[0][a[1]] }
      (index.size - 1).downto(0) do |i|
        if index[i] < self[i].size - 1
          index[i] += 1
          break
        else
          index[i] = 0
        end
      end
    end while index != [0] * size
  end
end

Cheers,
Dave

6

Yielding the values is certainly a good idea, but it makes the code a
lot bigger. Anyhow, here is the recursive, yielding version.

def cartprod(base, *others)
  if block_given?
    if others.empty?
      base.each{|a| yield [a]}
    else
      base.each do | a |
  cartprod(*others) do | b |
    yield [a, *b]
  end
      end
    end
    nil
  else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject() { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
  end
end

···

On 12/08/05, Dave Burt <dave@burt.id.au> wrote:

Brian Schröder offered:
> def cartprod(base, *others)
> return base.map{|a| [a] } if others.empty?
> others = cartprod(*others)
> base.inject() { | r, a | others.inject(r) { | r, b | r << ([a,
> *b]) } }
> end

Wow - that's nice and functional!

My procedural solution is much uglier, but it 1) isn't recursive and 2)
yields results to a given block as it iterates.

If given a block, the following will return nil, but pass the values into a
given block:

a=[[1,2,3],[4,5,6],[7,8,9]]
a.cartprod do |a0e, a1e, a2e|
  # ...
end

class Array
  def cartprod

    unless block_given?
      ret =
      cartprod {|tuple| ret << tuple}
      return ret
    end
    return if any? {|a| a.size == 0 }
    index = [0] * size
    begin
      yield *zip(index).map {|a| a[0][a[1]] }
      (index.size - 1).downto(0) do |i|
        if index[i] < self[i].size - 1
          index[i] += 1
          break
        else
          index[i] = 0
        end
      end
    end while index != [0] * size
  end
end

Cheers,
Dave

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

7

I've got some interesting benchmark results to share:
Benchmark.bm(35) do | b |
  [[2, 16], [6,7], [25,4], [800,2]].each do | size, depth |
    args = Array.new(depth) { Array.new(size) {|i| i} }
    b.report("Recursive Array (#{size}**#{depth})") do cartprod(*args) end
    b.report("Recursive Array iterated (#{size}**#{depth})") do
cartprod(*args).each do | e | end end
    b.report("Recursive Yielding (#{size}**#{depth})") do
cartprod_y(*args) do | e | end end
    b.report("Procedural Yielding (#{size}**#{depth})") do
args.cartprod do | *e | end end
    puts
  end
end

                                         user system total real
Recursive Array (2**16) 0.610000 0.130000 0.740000 ( 0.840845)
Recursive Array iterated (2**16) 0.890000 0.130000 1.020000 ( 1.287632)
Recursive Yielding (2**16) 3.910000 0.760000 4.670000 ( 4.779378)
Procedural Yielding (2**16) 4.850000 0.890000 5.740000 ( 5.847342)

Recursive Array (6**7) 1.690000 0.310000 2.000000 ( 2.027407)
Recursive Array iterated (6**7) 2.300000 0.430000 2.730000 ( 2.721382)
Recursive Yielding (6**7) 5.830000 1.330000 7.160000 ( 7.166822)
Procedural Yielding (6**7) 11.200000 1.970000 13.170000 ( 13.440081)

Recursive Array (25**4) 1.750000 0.360000 2.110000 ( 2.118353)
Recursive Array iterated (25**4) 1.990000 0.510000 2.500000 ( 2.507274)
Recursive Yielding (25**4) 9.130000 1.050000 10.180000 ( 10.220420)
Procedural Yielding (25**4) 12.020000 2.120000 14.140000 ( 15.580462)

Recursive Array (800**2) 3.750000 0.630000 4.380000 ( 4.375153)
Recursive Array iterated (800**2) 3.050000 0.790000 3.840000 ( 3.839810)
Recursive Yielding (800**2) 5.380000 0.930000 6.310000 ( 6.308811)
Procedural Yielding (800**2) 17.170000 2.480000 19.650000 ( 20.676642)

In these benchmarks the recursive version is a lot faster. Beware that
only creating and discarding the block is not a good measure,
therefore I also included an iteration about the returned array for
the array method. As you see it depends on the characteristics of the
argument which method is fastest.

regards,

Brian

···

On 12/08/05, Brian Schröder <ruby.brian@gmail.com> wrote:

On 12/08/05, Dave Burt <dave@burt.id.au> wrote:
> Brian Schröder offered:
> > def cartprod(base, *others)
> > return base.map{|a| [a] } if others.empty?
> > others = cartprod(*others)
> > base.inject() { | r, a | others.inject(r) { | r, b | r << ([a,
> > *b]) } }
> > end
>
> Wow - that's nice and functional!
>
> My procedural solution is much uglier, but it 1) isn't recursive and 2)
> yields results to a given block as it iterates.
>
> If given a block, the following will return nil, but pass the values into a
> given block:
>
> a=[[1,2,3],[4,5,6],[7,8,9]]
> a.cartprod do |a0e, a1e, a2e|
> # ...
> end
>
> class Array
> def cartprod
>
> unless block_given?
> ret =
> cartprod {|tuple| ret << tuple}
> return ret
> end
> return if any? {|a| a.size == 0 }
> index = [0] * size
> begin
> yield *zip(index).map {|a| a[0][a[1]] }
> (index.size - 1).downto(0) do |i|
> if index[i] < self[i].size - 1
> index[i] += 1
> break
> else
> index[i] = 0
> end
> end
> end while index != [0] * size
> end
> end
>
> Cheers,
> Dave
>
>
>
>

Yielding the values is certainly a good idea, but it makes the code a
lot bigger. Anyhow, here is the recursive, yielding version.

def cartprod(base, *others)
  if block_given?
    if others.empty?
      base.each{|a| yield [a]}
    else
      base.each do | a |
        cartprod(*others) do | b |
          yield [a, *b]
        end
      end
    end
    nil
  else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject() { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
  end
end

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

8

Hello,

Yielding the values is certainly a good idea, but it makes the code a
lot bigger. Anyhow, here is the recursive, yielding version.

def cartprod(base, *others)
  if block_given?
    if others.empty?
      base.each{|a| yield [a]}
    else
      base.each do | a |
cartprod(*others) do | b |
  yield [a, *b]
end
      end
    end
    nil # <--Why?
  else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
*b]) } }
  end
end

···

--
http://ruby.brian-schroeder.de/

## Question: Why the nil?

9

Interesting benchmarks. Thanks for sharing these and your code, Brian.

I was initially surprised that your recursive code was quicker than my
procedural, but when you look at them, it's obvious that my code is just
doing more, unnecessarily, while yours is nice and simple.

Any tips on learning to write code like your 3-line functonal recursive
cartprod?

Cheers,
Dave

10

because otherwise the function would return the base array when
invoked with a block. And that would not make any sense for method
chaining. Nil will invoke an exception if a chained method is called
upon it.

regards,

Brian

···

On 12/08/05, walter a kehowski <wkehowski@cox.net> wrote:

Hello,

Yielding the values is certainly a good idea, but it makes the code a
lot bigger. Anyhow, here is the recursive, yielding version.

def cartprod(base, *others)
  if block_given?
    if others.empty?
      base.each{|a| yield [a]}
    else
      base.each do | a |
cartprod(*others) do | b |
  yield [a, *b]
end
      end
    end
    nil # <--Why?
  else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject() { | r, a | others.inject(r) { | r, b | r << ([a,
*b]) } }
  end
end

## Question: Why the nil?

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

11

Thanks Dave,

regarding the tips you requested. The only thing that helps is to
think about how to split the problem recursively. It is like an
inductive proof. So it helps to make lots of inductive proofs
throughout your studies and get into a mindset for this. Then the
solution comes naturally. All a matter of experience I suppose (Though
I don't have that much, there are lots of more experienced people
here.)
Sorry if that is not of much help, maybe thinking about the proposed
solutions in this thread and the other threads will be more of a help.

best regards,

Brian

···

On 12/08/05, Dave Burt <dave@burt.id.au> wrote:

Interesting benchmarks. Thanks for sharing these and your code, Brian.

I was initially surprised that your recursive code was quicker than my
procedural, but when you look at them, it's obvious that my code is just
doing more, unnecessarily, while yours is nice and simple.

Any tips on learning to write code like your 3-line functonal recursive
cartprod?

Cheers,
Dave

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

12

Thanks, Brian.