Ruby: Generating subset of fixed length

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
  		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 }


['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 n^s, 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s