☘️ 🚶🏼 😦 Combinatoire en Python 🌠 🙏🏼 🐦

La bibliothèque Python standard, à partir de la version 2.2, fournit de nombreux outils pour générer des objets combinatoires, mais je n'ai pas pu trouver un seul article sur Internet qui expliquerait en détail comment travailler avec eux. J'ai donc décidé de corriger cette omission.

Pour commencer, je parlerai de la combinatoire et de ses formules de base. Si vous connaissez déjà cette section de mathématiques, vous pouvez ignorer ces paragraphes.

Supposons que nous ayons une chaîne composée de n lettres différentes et que nous voulons calculer toutes les façons de réorganiser ces lettres de manière à obtenir une nouvelle ligne. Pour la première position de la ligne, nous pouvons choisir l'une des n lettres que nous avons, pour la deuxième position l'une des n- 1ères lettres et ainsi de suite. On obtient ainsi le produit n (n-1) ... * 1 = n! le nombre de permutations de n éléments sans répétition .

Imaginez maintenant que le nombre de lettres dans une chaîne est limité. Nous avons n lettres disponibles et nous voulons calculer le nombre de façons d'en faire une chaîne de longueur k, où k <n, nous ne pouvons utiliser chaque lettre qu'une seule fois. Ensuite, nous pouvons mettre une des n lettres sur la première position de la ligne, l'une des n-1 lettres sur la deuxième position et l'une des n-k + 1 lettres sur la k-ème position. Le nombre total de lignes sera égal à n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! le nombre de placements de n à k . Si l'unicité des lettres n'est pas requise, alors nous obtenons la formule n ... n n = n ^ k le nombre de placements de n à k avec répétitions .

Avant cela, nous avons trié les séquences en tenant compte de l'ordre des éléments, et si l'ordre ne nous importait pas. Par exemple, nous avons n bonbons différents et nous voulons en choisir k à offrir à un ami, et k <n. Combien de façons existe-t-il de choisir k bonbons parmi n sans égard à la commande? La réponse est simple, au début, nous trouverons un placement de n par k sans répétition, mais ensuite les mêmes ensembles de bonbons ayant un ordre différent de leur séquence seront répétés. Combien de façons existe-t-il de réorganiser les k bonbons? C'est vrai, une permutation de k éléments sans répétition. La réponse finale: les placements de n par k sont divisés par des permutations de k sans répétitions. Formule $n! / (n-k)! / k!$ le nombre de combinaisons de n par k .

Considérez le cas plus compliqué, nous avons n boîtes qui contiennent chacune de nombreux bonbons du même goût, mais dans des boîtes différentes, les goûts sont différents. Combien y a-t-il de façons de faire un cadeau à un ami à partir de k bonbons, et quel peut être le même goût un certain nombre de fois? Puisque la commande n'a pas d'importance pour nous, organisons les bonbons cadeaux comme suit: au début, il y aura successivement des bonbons du premier goût, puis du second et ainsi de suite, et nous mettrons des correspondances entre des bonbons de goûts différents s'il n'y a pas de bonbons de tout goût dans notre cadeau - les allumettes qui étaient censées border ce goût à gauche et à droite se tiendront côte à côte. De plus, nous obtenons une séquence composée de k bonbons et n-1 correspondances, car il n'y a que n goûts et les correspondances les séparent. Notez maintenant que par l'emplacement des correspondances, nous pouvons restaurer l'ensemble d'origine. Ensuite, la réponse sera le nombre de façons de placer une correspondance n-1 dans une cellule n + k-1 sans prendre en compte l'ordre, qui est égal au nombre de combinaisons de n + k-1 par n-1, la formule: $(n + k-1)! / k! / (n-1)!$ le nombre de combinaisons de n à k avec répétitions .

Nous allons maintenant considérer plusieurs problèmes de combinatoire afin de consolider le matériau.

Tâche 1

Il y a 20 personnes, combien de façons de les associer
Solution: prenez la première personne, combien de façons il y a de choisir une paire pour lui: $inline$ , prenez la deuxième personne, combien de façons il y a de choisir une paire pour lui: $inline$ . Réponse: 19 !!! = 654729075

Tâche 2

Il y a 10 hommes et 10 filles, combien de façons de les répartir en entreprises composées du même nombre d'hommes et de filles, une entreprise vide n'est pas considéréeSolution:Méthode 1: le nombre de façons de monter une entreprise à partir d'un homme et d'une fille est égal au produit du nombre de façons de choisir une fille et du nombre de façons de choisir un homme. Le nombre de façons de choisir une fille sur 10 est égal à une combinaison de 10 à 1 sans répétition, il en est de même pour les hommes, donc nous allons cadrer. Ensuite, nous calculons de manière similaire les combinaisons de 10 à 2, de 10 à 3, et ainsi de suite à la combinaison de 10 à 10. La formule finale:

(10! / (10 - 1)! / 1!)^{2} + (10! / (10 - 2)! / 2!)^{2} + . . . + (10! / (10 - 10)! / 10!)^{2}

$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$ .
Méthode 2: considérez les nombreux hommes qui sont dans l'entreprise et les nombreuses filles qui ne sont pas dans son entreprise. Pour cet ensemble, vous pouvez définitivement restaurer l'entreprise et le nombre de personnes y est toujours égal à 10, car

k + (10 - k) = 10

$k + (10 - k) = 10$ , k - le nombre d'hommes dans l'entreprise,

$inline$ - le nombre de filles non incluses. Le nombre de ces ensembles est égal au nombre de combinaisons de 20 à 10, dans la réponse finale, nous soustraireons également un afin de ne pas prendre en compte la société vide quand il y a 10 filles dans notre ensemble. La formule finale:

$inline$ .

Donc, nous avons compris la théorie, maintenant nous allons apprendre à générer des objets combinatoires en utilisant la bibliothèque standard de python.
Nous travaillerons avec la bibliothèque itertools

from itertools import *

À l'aide de la fonction de permutations , vous pouvez générer toutes les permutations pour un objet itérable.

Exemple 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

Sur la base du deuxième appel, nous notons que les mêmes éléments dans des positions différentes sont considérés comme différents.

Exemple 2

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

Le placement diffère de la permutation par la limite du nombre de cellules disponibles

Exemple 3

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

Avec les dispositions de répétition, vous pouvez facilement parcourir toutes les chaînes de longueur fixe composées de caractères donnés

Exemple 4

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

En utilisant des combinaisons sans répétitions, vous pouvez parcourir tous les ensembles de lettres non répétitives d'une chaîne, d'un tableau ou d'un autre objet itérable donné sans égard à l'ordre

Exemple 5

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

Le résultat est similaire à des combinaisons d' appel, mais des ensembles avec les mêmes éléments sont également ajoutés au résultat.

Matériaux:
N.V. Gorbatchev "Collection de problèmes d'olympiades en mathématiques"
Documentation Python en russe

Combinatoire en Python