Working on a machine learning project I needed to compute all possible combinations of size 2 from a given array of elements. I could have easily used two loops to get the job done, but then its no fun. Also what if I need to generate all possible combinations of size 3 or 4 ?

Below is a much more generic solution that uses recursive calls, making the solution elegant and general for generating subset of any given size. Also I use “yield” command to avoid storage of computed subsets.

class Array
# Generate all possible combinations of given length
# @param:integer req_length -- number of elements in each combination
# @param: prefix -- used during recursive call. Ideally we should not expose prefix to user but define another function that calls this function and expose that function.
# @return -- combinations of req_length
def combination(req_length, prefix=[])
if(prefix.length == req_length)
yield prefix
else
slen = self.length
plen = prefix.length
endIndex = slen-req_length+plen
self[0..endIndex].each_with_index do |s, i|
self[i+1..slen].combination(req_length, prefix + [s]) {|i| yield i }
end
end
end
end
#Example
['a','b','c','d','e'].combination(2) {|i| puts i.inspect }

While the solution is working and is looking elegant, one question is still bothering me, namely time complexity. I am not able to determine what will be the time complexity. It looks like the time complexity of the above algorithm will be polynomial time bound, most likely to be , where n is the number of array elements and s is the subset size. Let me know if I am wrong and you have better estimate of the time complexity.

## Published by Ritesh Agrawal

I am a data scientist @ Uber. I work on making our data infrastructure (such as Hive, Presto, Vertica, etc) intelligent and efficient using data mining and machine learning techniques.
View all posts by Ritesh Agrawal