Análisis combinatorio y Python

Como recordarán (?), hace poco hablabamos del cálculo de factoriales. Pues bien, hoy vamos a usar este código para algo un poco más interesante como es el análisis combinatorio.

Análisis combinatorio sin repetición de elementos

Veamos primero como se comportan las combinaciones si no hay repetición:

Variaciones

Si hay un conjunto de n elementos, llamamos variación de orden r a todo subconjunto ordenado de r elementos extraido del conjunto de n elementos, sin repetir ningún elemento y siendo r

O sea, tenemos un subconjunto de r elementos pertenecientes al conjunto n y no podemos repetir los elementos. Lo que queremos saber es la cantidad de combinaciones posibles así, para eso podemos usar esta fórmula:

V_n,r=n!/[(n-r)]!

Entonces ya que tenemos el factorial, podemos hacer algo como esto:

def fact(n):
    if n==1:
        return 1
    else:
        return n*fact(n-1)

def variacionSR(n,r):
    return fact(n)/fact(n-r)

n=input("Ingrese conjunto: ")
r=input("Ingrese subconjunto: ")

print variacionSR(n,r)

Probándolo sabemos que extrayendo 8 elementos de un conjunto de 10 elementos tenemos 1814400 posibilidades.

Permutaciones

Llamamos permutaciones de orden r a toda ordenación de r elementos. O sea, es un caso particular de variación en la que r=n.

La fórmula sería algo así como esto:

P_r,r=r!/[(r-r)]!

Como el factorial de 0 es 1, la parte del divisor la podemos sacar. Este caso al final es más sencillo, ya que solo necesitamos el factorial.

Combinaciones

Dado un conjunto de n elementos, se llama combinación de orden r a los subconjuntos de r elementos extraidos del conjunto de n elementos sin repetir elementos y siendo r<=n.

La fórmula en este caso:

C_n,r=n!/[r!*(n-r)!]

Como ven todos los programas son similares, solo debemos hacer un pequeño cambio al programa de variaciones y obtenemos algo así:

def fact(n):
    if n==1:
        return 1
    else:
        return n*fact(n-1)

def CombinacionSR(n,r):
    return fact(n)/(fact(r)*fact(n-r))

n=input("Ingrese conjunto: ")
r=input("Ingrese subconjunto: ")

print CombinacionSR(n,r)

Y podemos sacar que por ejemplo sacando 4 de 10 tenemos 210 casos posibles.

Análisis combinatorio con repetición de elementos

Bueno, pero ahora que pasa si podemos repetir los elementos? La verdad las fórmulas no se vuelven tanto más complicadas, pero veamoslo:

Variaciones

En el caso de que se permitan repeticiones vamos a usar esto:

V’_n,r=n^r

Bueno, bastante sencillo no? El código es de lo más corto y encima ni siquiera necesitamos los factoriales.

def variacionCR(n,r):
    return n**r

n=input("Ingrese conjunto: ")
r=input("Ingrese subconjunto: ")

print variacionCR(n,r)

 Permutaciones

Por último tenemos las permutaciones, en este caso tenemos un conjunto de n elementos donde tenemos n1 elementos iguales y n2 elementos iguales, donde n=n1+n2 y llamamos permutación con repetición a toda ordenación de esos n elementos entre los cuales pueden haber repetidos.

La fórmula en este caso:

P’_n,n1,n2=n!/[n1!*n2!]

No es esto más complicado que el resto:

def fact(n):
    if n==1:
        return 1
    else:
        return n*fact(n-1)

def PermutacionCR(n,r):
    return fact(n)/(fact(r)*fact(n-r))

n=input("Ingrese conjunto: ")
r=input("Ingrese subconjunto de iguales (n1): ")

print PermutacionCR(n,r)