Combinatoria en Python

La biblioteca estándar de Python, comenzando con la versión 2.2, proporciona muchas herramientas para generar objetos combinatorios, pero no pude encontrar un solo artículo en Internet que explicara en detalle cómo trabajar con ellos. Por lo tanto, decidí corregir esta omisión.

Para empezar, hablaré sobre la combinatoria y sus fórmulas básicas. Si ya está familiarizado con esta sección de matemáticas, puede omitir estos párrafos.

Supongamos que tenemos una cadena que consta de n letras diferentes y queremos calcular todas las formas de reorganizar estas letras de manera que se obtenga una nueva línea. Para la primera posición en la línea, podemos elegir una de las n letras que tenemos, para la segunda posición una de las n- 1ras letras y así sucesivamente. Como resultado, obtenemos el producto n (n-1) ... * 1 = n! El número de permutaciones de n elementos sin repetición .

Ahora imagine que el número de letras en una cadena es limitado. Tenemos n letras disponibles y queremos calcular el número de formas de hacer una cadena de longitud k a partir de ellas, donde k <n, podemos usar cada letra solo una vez. Luego podemos poner una de las n letras en la primera posición de la línea, una de las letras n-1 en la segunda posición y una de las letras n-k + 1 en la posición k. El número total de líneas será igual a n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! el número de ubicaciones de n a k . Si no se requiere la unicidad de las letras, entonces obtenemos la fórmula n ... n n = n ^ k el número de ubicaciones de n a k con repeticiones .

Antes de eso, clasificamos las secuencias teniendo en cuenta el orden de los elementos y qué pasa si el orden no nos importa. Por ejemplo, tenemos n dulces diferentes y queremos elegir k de ellos para dárselos a un amigo, y k <n. ¿De cuántas maneras hay para elegir k caramelos de n sin importar el orden? La respuesta es simple, al principio encontraremos una colocación de n por k sin repetición, pero luego se repetirán los mismos conjuntos de dulces que tienen un orden diferente de su secuencia. ¿De cuántas maneras hay para reorganizar k dulces? Así es, una permutación de k elementos sin repetición. La respuesta final: las ubicaciones de n por k se dividen por permutaciones de k sin repeticiones. Formula $$$n! / (n-k)! / k!$El número de combinaciones de n por k .

Considere el caso más complicado, tenemos n cajas, cada una de las cuales contiene muchos dulces del mismo sabor, pero en diferentes cajas los gustos son diferentes. ¿De cuántas maneras hay para hacer un regalo a un amigo con k dulces, y qué puede ocurrir el mismo sabor varias veces? Como el pedido no nos importa, organicemos los dulces de regalo de la siguiente manera: al principio habrá sucesivamente dulces del primer sabor, luego del segundo y así sucesivamente, y pondremos fósforos entre dulces de diferentes gustos si no hay dulces de ningún sabor en nuestro regalo: los partidos que supuestamente bordearían este sabor a la izquierda y a la derecha se mantendrán uno al lado del otro. Además, obtenemos una secuencia que consta de k dulces y n-1 coincidencias, ya que solo hay n gustos y las coincidencias las separan. Ahora tenga en cuenta que por la ubicación de las coincidencias, podemos restaurar el conjunto original. Entonces la respuesta será el número de formas de colocar la coincidencia n-1 en la celda n + k-1 sin tener en cuenta el orden, que es igual al número de combinaciones de n + k-1 por n-1, la fórmula: $$$(n + k-1)! / k! / (n-1)!$El número de combinaciones de n a k con repeticiones .

Ahora consideraremos varios problemas en combinatoria para consolidar el material.

Tarea 1

Hay 20 personas, ¿cuántas maneras hay de emparejarlas?
Solución: tome la primera persona, cuántas maneras hay de elegir un par para él: $$$20-1 = 19$, tome la segunda persona, cuántas maneras hay de elegir un par para él: $$$20-2-1 = 17$. Respuesta: 19 !!! = 654729075

Tarea 2

Hay 10 hombres y 10 niñas, de cuántas maneras hay de dividirlos en compañías que consisten en el mismo número de hombres y niñas, no se considera una compañía vacía
Solución:
Método 1: la cantidad de formas de formar una empresa de un hombre y una niña es igual al producto de la cantidad de formas de elegir una niña y la cantidad de formas de elegir un hombre. La cantidad de formas de elegir una niña de cada 10 es igual a una combinación de 10 a 1 sin repetición, es similar con los hombres, por lo que vamos a cuadrar. A continuación, calculamos de manera similar las combinaciones de 10 a 2, de 10 a 3, y así sucesivamente a la combinación de 10 a 10. La fórmula final: $$$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$.
Método 2: considere los muchos hombres que están en la compañía y las muchas niñas que no están en su compañía. Para este conjunto, definitivamente puede restaurar la empresa, y la cantidad de personas en ella siempre es igual a 10, ya que $$$k + (10 - k) = 10$, k - el número de hombres en la empresa, $$$10 - k$- el número de chicas no incluidas en él. El número de tales conjuntos es igual al número de combinaciones de 20 a 10, en la respuesta final también restaremos uno para no tener en cuenta la compañía vacía cuando hay 10 chicas en nuestro conjunto. La fórmula final: $$$20! / (20-10)! / 10! - 1 = $ 18475$.

Entonces, descubrimos la teoría, ahora aprenderemos cómo generar objetos combinatorios usando la biblioteca estándar de Python.
Trabajaremos con la biblioteca itertools.

from itertools import * 

Usando la función de permutaciones , puede generar todas las permutaciones para un objeto iterable.

Ejemplo 1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba 

Según la segunda convocatoria, observamos que los mismos elementos en diferentes posiciones se consideran diferentes.

Ejemplo 2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb 

La ubicación difiere de la permutación por el límite en el número de celdas disponibles

Ejemplo 3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc 

Con diseños de repetición, puede iterar fácilmente sobre todas las cadenas de longitud fija que consisten en caracteres dados

Ejemplo 4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd 

Usando combinaciones sin repeticiones, puede iterar sobre todos los conjuntos de letras que no se repiten de una cadena, matriz u otro objeto iterable sin tener en cuenta el orden

Ejemplo 5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd 

El resultado es similar a las combinaciones de llamadas, pero también se agregan conjuntos con los mismos elementos al resultado.

Materiales:
N.V. Gorbachov "Colección de problemas olímpicos en matemáticas"
Documentación de Python en ruso