From: glen <glen83@...>
Date: 2006-12-14T10:22:44+09:00
Subject: array and hash combine methods

Just thought I'd post a solution I came up with to finding
combinations (as in, permutations and combinations) of arrays. For
example, combining:

[1,2] and [3,4,5]

should return:

[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

which is easy enough. But I wanted something that combine several
arrays at once, ie:

[[1,2],[3,4,5],[6,7]].combine
=> [[1, 3, 6], [1, 3, 7], [1, 4, 6], [1, 4, 7], [1, 5, 6], [1, 5, 7],
[2, 3, 6], [2, 3, 7], [2, 4, 6], [2, 4, 7], [2, 5, 6], [2, 5, 7]]

I had a look around and couldn't find anything that worked for more
than two arrays, so I wrote my own:

class Array
  #expects self to be an array of arrays, returns all the combinations possible
  def combine
    #checks
    output_length = 1
    periods = []
    reverse.each { |sub_arr|
      periods << output_length
      raise "combine needs an array of arrays!" if !sub_arr.is_a? Array
      raise "combine is meaningless unless all the sub_arrays have at
least one element!" if sub_arr.length == 0
      output_length *= sub_arr.length
    }
    periods.reverse!
    output = (1..output_length).map { Array.new(length) }
    output.each_index { |i|
      periods.each_index { |j|
        output[i][j] = self[j][(i/periods[j])%self[j].length]
      }
    }
    output
  end
end

And the corresponding hash method:

class Hash
  #expects a hash eg. {a=>[1,2], b=>[3,4]}
  #returns an array eg. [{a=>1,b=>3}, {a=>1,b=4}, {a=>2,b=>3}, {a=>2,b=4}]
  def combine
    values.combine.map { |comb|
      Hash[*keys.zip(comb).inject([]) { |arr,e| arr + e }]
    }
  end
end

I'd love to hear other solutions to this problem - and where I should
have looked to find them... Oh and if anyone has suggestions for a
better name than 'combine', that'd be great.

Cheers,
-glen.