I. IntroductionAprès les partitions d'un ensemble, on s'intéresse maintenant aux partitions d'un entier :
L'objectif sera cette fois de créer une fonction itérative en Python qui pourra générer la liste des partitions d'un entier quelconque.
On va ensuite montrer comment transformer ce code en une fonction génératrice qui va nous permettre d'obtenir les partitions sans avoir besoin de les stocker dans une liste.
II. Partitions d'un entier
II-A. Définition mathématique
En mathématiques, une partition d'un entier (parfois aussi appelée partage d'un entier) est une décomposition de cet entier en une somme d'entiers strictement positifs (appelés parties ou sommants), à l'ordre près des termes (à la différence du problème de composition tenant compte de l'ordre des termes).
Une telle partition est en général représentée par la suite des termes de la somme, rangés par ordre décroissant.
Prenons par exemple le nombre entier 5, les 7 partitions de 5 sont :
- 5 ;
- 4 + 1 ;
- 3 + 2 ;
- 3 + 1 + 1 ;
- 2 + 2 + 1 ;
- 2 + 1 + 1 + 1 ;
- 1 + 1 + 1 + 1 + 1.
Si on note 𝑝(n) le nombre de partitions de l'entier n, alors les premiers termes de la suite 𝑝(n) donnent :
𝑝(1) = 1, 𝑝(2) = 2, 𝑝(3) = 3, 𝑝(4) = 5, 𝑝(5) = 7, 𝑝(6) = 11, 𝑝(7) = 15, 𝑝(8) = 22, 𝑝(9) = 30, 𝑝(10) = 42, ...,
𝑝(50) = 204226, ..., 𝑝(100) = 190 569 292, ..., 𝑝(200) = 3 972 999 029 388, ...
On peut remarquer que la croissance de cette suite est très rapide.
II-B. Génération des partitions d'un entier
On va utiliser pour cela l'algorithme de construction décrit sur la page Wikipedia partition d'un entier :
La liste de toutes les partitions de 𝑛 dans l'ordre décroissant est donnée par un algorithme itératif.
Si une partition est représentée par une suite finie décroissante (𝑎𝑖) dont au moins un terme est strictement supérieur à 1, la partition suivante (𝑏𝑖) est construite comme suit :
On note 𝑘 le rang du dernier terme strictement supérieur à 1 et 𝑁 le nombre de termes qui valent 1 dans (𝑎𝑖).
Pour tout j < 𝑘, on définit 𝑏𝑗 = 𝑎𝑗.
On définit 𝑏𝑘 = 𝑎𝑘 − 1.
En notant 𝑁 + 1 = 𝑏𝑘𝑞 + 𝑟 la division euclidienne de 𝑁 + 1 par 𝑏𝑘, on définit les termes 𝑏𝑗 pour 𝑘 < 𝑗 < 𝑘 + 𝑞 + 1 par 𝑏𝑗 = 𝑏𝑘.
Si 𝑟 est non nul, on définit un dernier terme 𝑏𝑘+𝑞+1 = 𝑟.
On peut obtenir ainsi la liste des partitions pi de l'entier 5 :
L'objectif va être ensuite de traduire cet algorithme en Python.
III. Implémentation en Python
III-A. Génération de la liste des partitions d'un entier
On crée tout d'abord la fonction permettant de passer de la partition pi à la partition pi+1 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | def partition_suivante(a, k, N): # Construit la partition b qui suit la partition a dans la liste des partitions. # a : liste des entiers représentant la partition passée en argument # k : rang du dernier entier dans a strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans la liste a # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2] b = a[:k] # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1] b.append(a[k]-1) # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k] # On obtient le quotient q et le reste r de cette division. q = (N+1) // b[k] ; r = (N+1) % b[k] # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1] b = b + q*[b[k]] # Si le reste r est non nul. if r!=0: # ou : if r: # On ajoute l'entier r à la liste b : b[k+q+1] = r b.append(r) # calcul des valeurs de k et N pour la nouvelle partition b while (b[k]!=1): k+=1 if k==len(b): break # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b return (b, k-1, len(b) - k) |
Enfin, on crée la fonction principale permettant de générer la liste des partitions de l'entier n :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | def generer_partitions(n): # Fonction principale permettant de générer la liste des partitions de l'entier n. # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]] # 1re partition de la liste p = [n] # initialisation de la liste avec la 1re partition [n] partitions = [p] # initialisation des variables k et N # k : rang du dernier entier de [n] strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans [n] # k=-1 et N=1 si n=1, sinon k=0 et N=0 (k, N) = (-1, 1) if n==1 else (0, 0) # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle while k>=0: # appel de la fonction renvoyant la partition suivant p, avec les paramètres k et N p, k, N = partition_suivante(p, k, N) # ajout de la nouvelle partition à la liste partitions.append(p) # renvoi de la liste des partitions : [5], [4,1], [3,2], ..., [1, 1, 1, 1, 1,]] return partitions |
Testons maintenant la fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 | # Nombre entier dont on souhaite générer les partitions. n = 5 # version n°1 : création de la liste des partitions de l'entier de départ partitions = generer_partitions(n) # Affiche les partitions une à une. for partition in partitions: print(tuple(partition)) |
Le code affiche :
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
III-B. Fonction génératrice avec yield
Comme on l'a vu précédemment, le nombre de partitions croît très rapidement quand l'entier n augmente, ce qui risque d'entrainer des problèmes de mémoire insuffisante (MemoryError, ...).
On peut dans ce cas utiliser à la place une fonction génératrice qui va créer à la demande l'élément suivant de la séquence sans avoir besoin de le stocker dans une liste, permettant ainsi d’économiser de la mémoire.
Pour cela, Python dispose de l'instruction yield qui permet de transformer une fonction en générateur :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def generateur_partitions(n): # Fonction génératrice permettant de parcourir les partitions de l'entier n. # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]] # 1re partition de la liste p = [n] # renvoi de la 1re partition yield p # initialisation des variables k et N # k : rang du dernier entier de [n] strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans [n] # k=-1 et N=1 si n=1, sinon k=0 et N=0 (k, N) = (-1, 1) if n==1 else (0, 0) # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle. while k>=0: # appel de la fonction renvoyant la partition qui suit p, avec les paramètres k et N p, k, N = partition_suivante(p, k, N) # renvoi de la nouvelle partition p yield p |
Testons maintenant la fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 | # Nombre entier dont on souhaite générer les partitions. n = 5 # version n°2 : création du générateur permettant de parcourir la liste des partitions de l'entier de départ gen_partitions = generateur_partitions(n) # Affiche les partitions une à une. for partition in gen_partitions: print(tuple(partition)) |
Le code affiche :
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
III-C. Module complet
On donne enfin le code complet du module pour effectuer les tests :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | def partition_suivante(a, k, N): # Construit la partition b qui suit la partition a dans la liste des partitions. # a : liste des entiers représentant la partition passée en argument # k : rang du dernier entier dans a strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans la liste a # pour tout j < k, on définit b[j] = a[j] : a = [2, 2, 1] -> b = [2] b = a[:k] # On ajoute (a[k] - 1) à la liste b : b[k] = a[k] - 1 : a = [2, 2, 1] -> b = [2, 1] b.append(a[k]-1) # En notant N+1 = b[k]*q + r la division euclidienne de N+1 par b[k] # On obtient le quotient q et le reste r de cette division. q = (N+1) // b[k] ; r = (N+1) % b[k] # On évalue ensuite les entiers b[j] = b[k] pour k < j < k + q + 1 : a = [2, 2, 1] -> b = [2, 1] + 2*[1] = [2, 1, 1, 1] b = b + q*[b[k]] # Si le reste r est non nul. if r!=0: # ou : if r: # On ajoute l'entier r à la liste b : b[k+q+1] = r b.append(r) # calcul des valeurs de k et N pour la nouvelle partition b while (b[k]!=1): k+=1 if k==len(b): break # renvoi de la partition b suivant la partition a, du rang k dans b, et du nombre N d'entiers valant 1 dans b return (b, k-1, len(b) - k) def generer_partitions(n): # Fonction principale permettant de générer la liste des partitions de l'entier n. # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]] # 1re partition de la liste p = [n] # initialisation de la liste avec la 1re partition [n] partitions = [p] # initialisation des variables k et N # k : rang du dernier entier de [n] strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans [n] # k=-1 et N=1 si n=1, sinon k=0 et N=0 (k, N) = (-1, 1) if n==1 else (0, 0) # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle while k>=0: # appel de la fonction renvoyant la partition suivant p, avec les paramètres k et N p, k, N = partition_suivante(p, k, N) # ajout de la nouvelle partition à la liste partitions.append(p) # renvoi de la liste des partitions : [5], [4,1], [3,2], ..., [1, 1, 1, 1, 1,]] return partitions def generateur_partitions(n): # Fonction génératrice permettant de parcourir les partitions de l'entier n. # Partitions dont les termes sont rangés dans l'ordre décroissant : [[5], [4, 1], [3, 2], ..., [1, 1, 1, 1, 1,]] # 1re partition de la liste p = [n] # renvoi de la 1re partition yield p # initialisation des variables k et N # k : rang du dernier entier de [n] strictement supérieur à 1 # N : nombre d'entiers qui valent 1 dans [n] # k=-1 et N=1 si n=1, sinon k=0 et N=0 (k, N) = (-1, 1) if n==1 else (0, 0) # Tant que k est supérieur ou égal à 0 : si k=-1 on sort de la boucle. while k>=0: # appel de la fonction renvoyant la partition qui suit p, avec les paramètres k et N p, k, N = partition_suivante(p, k, N) # renvoi de la nouvelle partition p yield p # Nombre entier dont on souhaite générer les partitions. n = 5 # Affiche le nombre entier. print("Partitions de " + str(n)) print() print("Génération des partitions de l'entier..\n") print("I. Version n°1 : méthode classique\n") # version n°1 : génère la liste des partitions de l'entier n partitions = generer_partitions(n) print("Liste des partitions de n :\n") # Affiche les partitions une à une. for partition in partitions: print(tuple(partition)) print() print("II. Version n°2 : fonction génératrice avec yield\n") # version n°2 : crée le générateur permettant de parcourir la liste des partitions de l'entier de départ gen_partitions = generateur_partitions(n) print("Liste des partitions de n :\n") # Affiche les partitions une à une. for partition in gen_partitions: print(tuple(partition)) |
IV. Conclusion
Après avoir décrit l'algorithme permettant d'obtenir les partitions d'un entier, on a donc pu générer en Python la liste des partitions d'un entier quelconque.
Enfin, on a créé une fonction génératrice à partir de ce code, pour éviter les problèmes de mémoire insuffisante.
Sources :
https://fr.wikipedia.org/wiki/Partition_d%27un_entier
https://fr.wikiversity.org/wiki/Algo...it%C3%A9rative
https://gayerie.dev/docs/python/pyth...es-generateurs