Creating Combinations of Sets/Arrays/Things in Ruby
I was looking for a way to create combinations of things in Ruby and I found an article by Uncle Bob detailing his attempt at writing a combination generator in Ruby. I modified it slightly to use an array of items, instead of simple indexes.
require 'pp'
def choose(n, k)
return [[]] if n.nil? || n.empty? && k == 0
return [] if n.nil? || n.empty? && k > 0
return [[]] if n.size > 0 && k == 0
c2 = n.clone
c2.pop
new_element = n.clone.pop
choose(c2, k) + append_all(choose(c2, k-1), new_element)
end
def append_all(lists, element)
lists.map { |l| l << element }
end
all = [:a, :b, :c, :d]
pp choose(all,3)
The above code prints out:
[[:a, :b, :c], [:a, :b, :d], [:a, :c, :d], [:b, :c, :d]]If you don’t want these types of combinations, there is a Ruby library for calculating Permutations which will give you all the different permutations, or orderings, of a set of things.
Here’s an alternative version. I’m still not real pleased with it. I don’t like the inefficiency of slicing the array repeatedly, but probably the only way to avoid that is to use a set of indices to navigate through the array which would clutter things up.
Return all combinations of n elements from array
combinations([1,2,3],2) -> [[1,2],[1,3],[2,3]]
def combinations array, n
result = []
if n > 0
(0 .. array.length - n).each do |i|
combs = combinations(array[i + 1 .. -1], n - 1)
combs = [[]] if combs.empty?
combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
end
end
return result
end
Brian Adkins
10 Sep 07 at 8:09 am
boy that looks bad! Maybe you can wrap the code with <pre>
Brian Adkins
10 Sep 07 at 8:10 am
BTW you can combine your first and third line since they both have ‘k==0′ and both return [[]]
Brian Adkins
10 Sep 07 at 8:12 am