Factoriales, combinaciones y permutaciones

En matemática combinatoria, una combinación es una colección desordenada de elementos únicos. (Una colección ordenada se llama una permutación.) Siendo S, el conjunto de todos los elementos únicos posibles, una combinación es un subconjunto de los elementos de S. El orden de los elementos en una combinación no es importante (dos listas con los mismos elementos en distinto orden se consideran como la misma combinación). Además, los elementos no se pueden repetir en una combinación (cada elemento aparece únicamente una vez), lo que se refiere a menudo como "sin sustitución o repetición". Esto se debe a que las combinaciones son definidas por los elementos contenidos en ellas, el conjunto s { 1, 1, 1} es el mismo que {1}. Por ejemplo, de una baraja de 52 cartas 5 cartas cualquiera pueden formar una combinación válida (una mano). El orden de las cartas no importa y no pueden haber repeticiones de las cartas.

¿Como implementamos el operador combinación? Primero habrá que implementar el factorial:

Una implementación común de  factorial en Ruby, de primera instancia de la forma siguiente:

def factorial(n)
 if n > 1
  # casos mayor que 1, se usa la formula recursiva
  # n! = n*(n-1)!
  n * factorial(n-1)
 else
  # casos 0 y 1, devuelve 1
  1
 end
end

Pero se puede hacer mas compacto refactorandolo usando rangos.

def factorial(n)
  if n > 1
    (2..n).inject{|x,y| x*y}
  else
    1
end

Así que extendida a la clase Integers

class Integer
  def factorial
    if self > 1
      (2..self).inject{|x,y| x*y}
    else
      1
  end
end

Ahora definimos las combinaciones de n en k:

class Integer
  def combinaciones(k)
    ((self-k+1)..self).inject{|x,y| x*y} / k.factorial
  end
end

Para saber el número de "manos" de 5 cartas que tendríamos en un mazo de 52 es tan fácil como

>>52.combinaciones(5)
>>2598960

Ahora el número de permutaciones en un mazo de cartas, es decir el número de formas en que podríamos ordenar las 52 cartas es un número bastante grande, ya que es el factorial del número de elementos del conjunto.

>>52.factorial
>>80658175170943878571660636856403766975289505440883277824000000000000