glen
12/14/2006 1:23:00 AM
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.