Permutation and combination in ruby's arrays Wednesday. April 08, 2015 - 2 mins 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:

$latex \frac{n!}{(n-k)!} &s=4 $

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

$latex \frac{n!}{k!(n-k)!} = \binom{n}{k} &s=4 $

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:

To include the method `factorial`

to class `Fixnum`

. 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 :-)

Carles Hernandez-Ferrer Bioinformatics, data analysis and software development

Carles Hernandez-Ferrer © 2020