Permutation and Combination in Ruby’s Arrays

Today I was working on a simple kata of CodeWars that required to work with combinations and permutations of elements given in array.

The number of permutations of the n elements in a set taken by groups of k is given by:

\frac{n!}{(n-k)!}

In this case, the order within the groups matters. If order does not matter, then we are talking about combinations:

\frac{n!}{k!(n-k)!} = \binom{n}{k}

The array class from ruby comes with a method (permutation) to get the permutations of its elements given a value k:

[1,2].permutation(0).to_a
=> [[]]
[1,2].permutation(1).to_a
=> [[1], [2]]
[1,2].permutation(2).to_a
=> [[1, 2], [2, 1]]
[1,2].permutation(3).to_a
=> []

In the same way, the class array comes with a method combination to get the combinations of its elements given a value k:

[1,2].combination(0).to_a
=> [[]]
[1,2].combination(1).to_a
=> [[1], [2]]
[1,2].combination(2).to_a
=> [[1, 2]]
[1,2].combination(3).to_a
=> []

So with these two methods we can get the sets results of permuting and combining the elements of an array but not to calculate the elements of a k-permutation of k-combination.

To do that I propose:

  1. To include the method factorial to class Fixnum.
  2. To include the methods perm_length and comb_length to class array

These two steps can be done as:

class Fixnum
  def factorial
    f = 1
    (1..self).each{|ii| f *= ii }
    return f
  end
end

class Array
  def perm_length k
    return self.length.factorial / (self.length - k).factorial
  end
  def comb_length k
    return self.length.factorial / (k.factorial * (self.length - k).factorial)
  end
end

Something more complex would be needed for using this in a real scenario like a control for negative values of k. But for me it’s just enough :-)

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: