Generating combinations from multiple sets

ruby-talk
1

Dear all,

I have a requirement as below.

There are 'n' containers of lengths {l_i}, i = 1,..,n. All these
containers are collected into an array. Picking one element at a time
from each container, an array has to be constructed and either yielded
or accumulated.

I have written the following code that seems to work reasonably. Are
there simpler or more efficient ways of doing this?

Thanks in advance,

JS

* * * *

def generate_combinations(cont_ary, &blk)

   cont_count = cont_ary.length

   return if cont_count < 1

   if cont_count == 1
     if block_given?
       cont_ary[0].each { | el | yield [el] }
       return
     else
       return cont_ary[0].collect { | el | [el] }
     end
   end

   cur_indices = Array.new(cont_count, 0)
   combinations = []

   generate_combinations_iterator(cont_ary, 0, cur_indices,
                                  :working_set => Array.new(cont_count),
                                  :accumulator => combinations,
                                  &blk)

   return combinations unless block_given?

end

···

#

def generate_combinations_iterator(cont_ary, cur_cont, cur_indices, opts = {}, &blk)

   cont_ary[cur_cont].each_with_index do | el, i |

     opts[:working_set][cur_cont] = el

     case cur_cont
     when 0
       cur_indices[cur_cont] = i
       (1...cur_indices.length).each { | j | cur_indices[j] = 0 }
       generate_combinations_iterator(cont_ary, cur_cont + 1, cur_indices, opts, &blk)

     when cont_ary.length-1
       if block_given?
         yield opts[:working_set]
       else
         opts[:accumulator] << Array.new(opts[:working_set])
       end

     else
       cur_indices[cur_cont] = i
       generate_combinations_iterator(cont_ary, cur_cont + 1, cur_indices, opts, &blk)
     end

   end

end

#

Output
------

irb(main):011:0> load 'combination-generator.rb'
=> true

irb(main):012:0> ary1 = []
=> []

irb(main):013:0> generate_combinations(ary1)
=> nil

irb(main):014:0> ary2 = [[1, 2, 3, 4]]
=> [[1, 2, 3, 4]]

irb(main):015:0> pp generate_combinations(ary2)
[[1], [2], [3], [4]]
=> nil

irb(main):016:0> ary3 = [[1, 2, 3, 4], ['a', 'b', 'c']]
=> [[1, 2, 3, 4], ["a", "b", "c"]]

irb(main):017:0> pp generate_combinations(ary3)
[[1, "a"],
  [1, "b"],
  [1, "c"],
  [2, "a"],
  [2, "b"],
  [2, "c"],
  [3, "a"],
  [3, "b"],
  [3, "c"],
  [4, "a"],
  [4, "b"],
  [4, "c"]]
=> nil

2

In case the gateway is broken again:

I have a shorter alternative; it may be more efficient but you'll have to
test that for yourself:

def all_combinations(enum,&bl)
  pre = ""
  post = ""
  middle = []
  enum.each_with_index do |en,idx|
    item = "e#{idx}"
    pre << "enum[" << idx.to_s << "].each {|" << item << "| "
    middle << item
    post << "}"
  end
  eval(pre << "bl[" << middle.join(",") << "]" << post)
end

irb(main):053:0> all_combinations([[1,2,3],%w{a b c d}]) {|*a| p a}
[1, "a"]
[1, "b"]
[1, "c"]
[1, "d"]
[2, "a"]
[2, "b"]
[2, "c"]
[2, "d"]
[3, "a"]
[3, "b"]
[3, "c"]
[3, "d"]
=> [1, 2, 3]

You can even change this to work with arbitrary Enumerables - this version
depens on "enum" being an Array.

Kind regards

    robert

3

Thank you!

Preliminary testing seems to show that it indeed is faster. I think it is understandable since it is doing inline expansion, rather than recursion.

Nice use of code generation.

Best regards,

JS

Robert Klemme wrote:

···

In case the gateway is broken again:

I have a shorter alternative; it may be more efficient but you'll have to
test that for yourself:

def all_combinations(enum,&bl)
  pre = ""
  post = ""
  middle =
  enum.each_with_index do |en,idx|
    item = "e#{idx}"
    pre << "enum[" << idx.to_s << "].each {|" << item << "| "
    middle << item
    post << "}"
  end
  eval(pre << "bl[" << middle.join(",") << "]" << post)
end

irb(main):053:0> all_combinations([[1,2,3],%w{a b c d}]) {|*a| p a}
[1, "a"]
[1, "b"]
[1, "c"]
[1, "d"]
[2, "a"]
[2, "b"]
[2, "c"]
[2, "d"]
[3, "a"]
[3, "b"]
[3, "c"]
[3, "d"]
=> [1, 2, 3]

You can even change this to work with arbitrary Enumerables - this version
depens on "enum" being an Array.

Kind regards

    robert