# Generating combinations from multiple sets

**URL:** <https://www.ruby-forum.com/t/generating-combinations-from-multiple-sets/52543>\
**Category:** Ruby\
**Created:** [January 16, 2006, 6:13am UTC](https://www.ruby-forum.com/t/generating-combinations-from-multiple-sets/52543 "2006-01-16T06:13:15Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Srinivas\_J](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/779978/32.png) [@Srinivas\_J](https://www.ruby-forum.com/u/Srinivas_J)\
**Post date:** [January 16, 2006, 6:13am UTC](https://www.ruby-forum.com/t/generating-combinations-from-multiple-sets/52543/1 "2006-01-16T06:13:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Srinivas\_J](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/779978/32.png) [@Srinivas\_J](https://www.ruby-forum.com/u/Srinivas_J)\
**Post date:** [January 16, 2006, 10:35am UTC](https://www.ruby-forum.com/t/generating-combinations-from-multiple-sets/52543/2 "2006-01-16T10:35:07Z")

</div>

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
```

---

<div class="post-metadata">

**Author:** ![Srinivas\_J](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/779978/32.png) [@Srinivas\_J](https://www.ruby-forum.com/u/Srinivas_J)\
**Post date:** [January 16, 2006, 1:20pm UTC](https://www.ruby-forum.com/t/generating-combinations-from-multiple-sets/52543/3 "2006-01-16T13:20:48Z")

</div>

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