Generating all tuples (Ruby)

From LiteratePrograms

Other implementations: Haskell | Lisp | Perl | Python | Ruby

This is a simple example of the tuples generation algorithm, written in Ruby.

see The Art of Computer Programming (TAOCP) Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005), ISBN 0-201-85393-0

Algorithm M

The generation function is genTuplesM as below:

• Input parameter: we list the limits on each bit into a list as an input
• Output: generating all possible tuples

<<genTuplesM.rb>>=
def genTuplesM(lst)
  lst.inject([[]]) { |prev, b| prev.inject([]) { |acc, xs| acc + (1..b).collect { |i| xs + [i] } } }
end
genTuplesM([3,5,3,2])

Alternatively, using product() in Ruby 1.8.7 and later:

<<genTuplesM2.rb>>=
def genTuplesM(lst)
  (1..lst[0]).to_a.product(*lst[1..-1].collect{|b| (1..b).to_a})
end
genTuplesM([3,5,3,2])

Test

Just load the file genTuplesM.rb in Ruby, execute it and you will get the result.

Download code