Generating combinations from multiple sets

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

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

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs