Forum: Ruby Generating combinations from multiple sets

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
1e7d80da752f10d223599a3600aed1d2?d=identicon&s=25 Srinivas Jonnalagadda (Guest)
on 2006-01-16 06:13
(Received via mailing list)
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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-01-16 10:35
(Received via mailing list)
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
1e7d80da752f10d223599a3600aed1d2?d=identicon&s=25 Srinivas Jonnalagadda (Guest)
on 2006-01-16 13:20
(Received via mailing list)
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 topic is locked and can not be replied to.