Analyse combinatoire et Python : les combinaisons avec r�p�tition

Un billet blog de Denis Hulo

Le 4 avril 2024, par User

0PARTAGES

I. Introduction

Apr�s les combinaisons sans r�p�tition, on s'int�resse maintenant aux combinaisons avec r�p�tition :

L'objectif sera cette fois de cr�er une fonction en Python qui pourra g�n�rer la liste des combinaisons avec r�p�tition de k �l�ments pris dans un ensemble de n �l�ments.

On va ensuite montrer comment transformer ce code en une fonction g�n�ratrice qui va nous permettre d'obtenir les combinaisons sans avoir besoin de les stocker dans une liste.

II. Combinaisons avec r�p�tition

D'apr�s Wikipedia, en analyse combinatoire, une combinaison avec r�p�tition est une combinaison o� donc l'ordre des �l�ments n'importe pas et o�, contrairement � une combinaison classique (sans r�p�tition), chaque �l�ment de la combinaison peut appara�tre plusieurs fois.

Par exemple, lorsque dix d�s � six faces (num�rot�es de 1 � 6) sont jet�s, le r�sultat fourni par ces dix d�s, si l'ordre dans lequel sont jet�s les d�s n'est pas pris en compte, (par exemple un 2, trois 4, deux 5 et quatre 6, sans retenir � quel d� pr�cis�ment correspond chaque face) est une combinaison des diff�rentes faces apparaissant sur chaque d�, et o� chaque face peut appara�tre plusieurs fois.

Cette exp�rience peut �tre mod�lis�e par une loi multinomiale dans laquelle chaque combinaison possible est associ�e � un coefficient multinomial.

Dans un jeu de dominos, les 28 pi�ces repr�sentent les combinaisons avec r�p�tition de 2 �l�ments pris dans un ensemble E = {blanc, 1, 2, 3, 4 ,5, 6} � 7 �l�ments.

Le nombre de combinaisons avec r�p�tition de k �l�ments pris dans un ensemble � n �l�ments est �gal au nombre de k-combinaisons (sans r�p�tition) de n + k � 1 �l�ments :

On peut remarquer avec cette formule que le nombre de combinaisons croit rapidement quand k et n augmentent.

III. G�n�ration des combinaisons avec r�p�tition

Prenons par exemple un ensemble de n=3 �l�ments :

E = {a, b, c}

On souhaite obtenir la liste des combinaisons de k=4 �l�ments pris avec remise dans l'ensemble E, c'est-�-dire g�n�rer la liste des 4-combinaisons avec r�p�tition :

(a, a, a, a), (a, a, a, b), ..., (c, c, c, c).

On va d'abord associer � chaque �l�ment de cet ensemble un indice d�butant � 0 comme en Python :

(a, b, c) → (0, 1, 2)

On g�n�re ensuite les 4-uplets ou quadruplets d'indices (i₀, i₁, i₂, i₃) (croissants au sens large) et leur combinaison, du premier (0, 0, 0, 0) au dernier (2, 2, 2, 2), dans cet ordre :

(0, 0, 0, 0) → (a, a, a, a)
(0, 0, 0, 1) → (a, a, a, b)
(0, 0, 0, 2) → (a, a, a, c)
(0, 0, 1, 1) → (a, a, b, b)
(0, 0, 1, 2) → (a, a, b, c)
(0, 0, 2, 2) → (a, a, c, c)
(0, 1, 1, 1) → (a, b, b, b)
(0, 1, 1, 2) → (a, b, b, c)
(0, 1, 2, 2) → (a, b, c, c)
(0, 2, 2, 2) → (a, c, c, c)
(1, 1, 1, 1) → (b, b, b, b)
(1, 1, 1, 2) → (b, b, b, c)
(1, 1, 2, 2) → (b, b, c, c)
(1, 2, 2, 2) → (b, c, c, c)
(2, 2, 2, 2) → (c, c, c, c)

On incr�mente donc � chaque fois les indices des k-uplets (i₀, i₁, i₂, i₃) en commen�ant par la droite, un peu comme pour les chiffres des nombres entiers, mais de fa�on � toujours conserver un ordre croissant des indices i₀ ≤ i₁ ≤ i₂ ≤ i₃ ≤ 2.

Dans le m�me temps, on transforme chaque k-uplet d'indices croissants en une k-combinaison d'�l�ments de E en utilisant la correspondance entre indices et �l�ments de E : (0, 1, 2) → (a, b, c).

IV. Impl�mentation en Python

IV-A. G�n�ration des combinaisons avec r�p�tition

On pr�sente maintenant une fonction qui g�n�re la liste des combinaisons avec r�p�tition de k �l�ments pris dans un ensemble de n �l�ments :

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
def generer_combinaisons(elements, k): 
    # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments 
    # generer_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') 
  
    # nombre d'éléments de l'ensemble 
    n = len(elements) 
  
    # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') 
    indices = [0] * k 
  
    # On crée la 1re combinaison à partir de la liste d'indices. ex. : [0, 0, 0] → ('a', 'a', 'a') 
    k_combinaison = tuple(elements[i] for i in indices) 
  
    # initialisation de la liste avec la 1re combinaison 
    k_combinaisons = [k_combinaison] 
  
    # tant que vrai 
    while True: 
  
        # parcours des indices de la liste 
        for i in reversed(range(k)): 
            # Si la valeur de l'indice est différente de n-1. 
            if indices[i] != n - 1: 
                break # On sort de la boucle : indice trouvé 
        else: # sinon 
            break # On sort de la boucle. 
  
        # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste  
        indices[i:] = [indices[i] + 1] * (k - i) 
  
        # On génère la combinaison correspondant à la liste d'indices. 
        k_combinaison = tuple(elements[i] for i in indices) 
  
        # ajout de la combinaison à la liste 
        k_combinaisons.append(k_combinaison) 
  
    # renvoi la liste des combinaisons 
    return k_combinaisons

Le code est bas� sur la fonction combinations_with_replacement pr�sent�e dans la documentation du module itertools.

Testons maintenant la fonction :

Code Python :

S�lectionner tout

1
2
3
4
5
6
7
8
9
10
11
# valeur de k 
k = 4 
  
# création de la liste d'éléments 
elements = ['a','b','c'] 
  
# Génère la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. 
combinaisons = generer_combinaisons(elements, k) 
  
# Affiche la liste des combinaisons. 
print(combinaisons)

Le code affiche :

[('a', 'a', 'a', 'a'), ('a', 'a', 'a', 'b'), ('a', 'a', 'a', 'c'), ('a', 'a', 'b', 'b'), ('a', 'a', 'b', 'c'), ('a', 'a', 'c', 'c'), ('a', 'b', 'b', 'b'), ('a', 'b', 'b', 'c'), ('a', 'b', 'c', 'c'), ('a', 'c', 'c', 'c'), ('b', 'b', 'b', 'b'), ('b', 'b', 'b', 'c'), ('b', 'b', 'c', 'c'), ('b', 'c', 'c', 'c'), ('c', 'c', 'c', 'c')]

IV-B. Fonction g�n�ratrice avec yield

Comme on l'a vu pr�c�demment, le nombre de combinaisons cro�t tr�s rapidement quand les param�tres k et n augmentent, 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 la fonction pr�c�dente 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
26
27
28
def generateur_combinaisons(elements, k): 
    # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments 
    # generateur_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') 
  
    # nombre d'éléments de l'ensemble 
    n = len(elements) 
  
    # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') 
    indices = [0] * k 
  
    # On génère la 1re combinaison. ex. : [0, 0, 0] → ('a', 'a', 'a') 
    yield tuple(elements[i] for i in indices) 
  
    while True: 
  
        # parcours des indices de la liste indices 
        for i in reversed(range(k)): 
            # Si la valeur de l'indice est différente de n-1 
            if indices[i] != n - 1: 
                break # On sort de la boucle : indice trouvé 
        else: 
            return 
  
        # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste 
        indices[i:] = [indices[i] + 1] * (k - i) 
  
        # On génère la combinaison correspondant aux indices. 
        yield tuple(elements[i] for i in indices)

Vous pouvez retrouver cette fonction dans la documentation du module itertools.

Testons la maintenant :

Code Python :

S�lectionner tout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# valeur de k 
k = 4 
  
# création de la liste d'éléments 
elements = ['a','b','c'] 
  
# Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. 
gen_combinaisons = generateur_combinaisons(elements, k) 
  
print("Liste des combinaisons avec répétitions :\n") 
  
# Affiche les combinaisons une à une. 
for combinaison in gen_combinaisons: 
    print(combinaison)

Le code affiche :

Liste des combinaisons avec r�p�tition :

('a', 'a', 'a', 'a')
('a', 'a', 'a', 'b')
('a', 'a', 'a', 'c')
('a', 'a', 'b', 'b')
('a', 'a', 'b', 'c')
('a', 'a', 'c', 'c')
('a', 'b', 'b', 'b')
('a', 'b', 'b', 'c')
('a', 'b', 'c', 'c')
('a', 'c', 'c', 'c')
('b', 'b', 'b', 'b')
('b', 'b', 'b', 'c')
('b', 'b', 'c', 'c')
('b', 'c', 'c', 'c')
('c', 'c', 'c', 'c')

IV-C. Application : g�n�ration des triplets (x, y, z) tels que x + y + z = 4

D�terminer les triplets (x, y, z) de ℕ³ tels que x + y + z = 4.

On peut se dire que l'on a trois types d'objets : ceux du type X, ceux du type Y et ceux du type Z. On doit en choisir 4 avec remise dans l'ensemble E = {X, Y, Z}. Le nombre x sera donn� par le nombre d'�l�ments du type X choisis, y par le nombre d'�l�ments du type Y et z par ceux du type Z :

Code Python :

S�lectionner tout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# valeur de k 
k = 4 
  
# création de la liste d'éléments 
elements = ['X', 'Y', 'Z'] 
  
# Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. 
gen_combinaisons = generateur_combinaisons(elements, k) 
  
print("Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :\n") 
  
# Affiche les triplets (x, y, z) tels que x + y + z = 4. 
for combinaison in gen_combinaisons: 
    # détermination du nombre de 'X', de 'Y' et de 'Z' pour chaque combinaison 
    x, y, z = combinaison.count("X"), combinaison.count("Y"), combinaison.count("Z") 
  
    # Affiche la combinaison et son triplet (x, y, z). 
    print(str(combinaison) + " → " + str((x, y, z)))

Le code affiche :

Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :

('X', 'X', 'X', 'X') → (4, 0, 0)
('X', 'X', 'X', 'Y') → (3, 1, 0)
('X', 'X', 'X', 'Z') → (3, 0, 1)
('X', 'X', 'Y', 'Y') → (2, 2, 0)
('X', 'X', 'Y', 'Z') → (2, 1, 1)
('X', 'X', 'Z', 'Z') → (2, 0, 2)
('X', 'Y', 'Y', 'Y') → (1, 3, 0)
('X', 'Y', 'Y', 'Z') → (1, 2, 1)
('X', 'Y', 'Z', 'Z') → (1, 1, 2)
('X', 'Z', 'Z', 'Z') → (1, 0, 3)
('Y', 'Y', 'Y', 'Y') → (0, 4, 0)
('Y', 'Y', 'Y', 'Z') → (0, 3, 1)
('Y', 'Y', 'Z', 'Z') → (0, 2, 2)
('Y', 'Z', 'Z', 'Z') → (0, 1, 3)
('Z', 'Z', 'Z', 'Z') → (0, 0, 4)

IV-D. Module complet

On donne pour finir le code complet contenant les fonctions permettant de g�n�rer ces combinaisons :

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
125
126
127
128
129
130
131
132
133
134
135
def generer_combinaisons(elements, k): 
    # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments 
    # generer_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') 
  
    # nombre d'éléments de l'ensemble 
    n = len(elements) 
  
    # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') 
    indices = [0] * k 
  
    # On crée la 1re combinaison à partir de la liste d'indices. ex. : [0, 0, 0] → ('a', 'a', 'a') 
    k_combinaison = tuple(elements[i] for i in indices) 
  
    # initialisation de la liste avec la 1re combinaison 
    k_combinaisons = [k_combinaison] 
  
    # tant que vrai 
    while True: 
  
        # parcours des indices de la liste 
        for i in reversed(range(k)): 
            # Si la valeur de l'indice est différente de n-1. 
            if indices[i] != n - 1: 
                break # On sort de la boucle : indice trouvé 
        else: # sinon 
            break # On sort de la boucle. 
  
        # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste  
        indices[i:] = [indices[i] + 1] * (k - i) 
  
        # On génère la combinaison correspondant à la liste d'indices. 
        k_combinaison = tuple(elements[i] for i in indices) 
  
        # ajout de la combinaison à la liste 
        k_combinaisons.append(k_combinaison) 
  
    # renvoi la liste des combinaisons 
    return k_combinaisons 
  
  
def generateur_combinaisons(elements, k): 
    # fonction permettant de générer la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments 
    # generateur_combinaisons(['a','b','c'], 2) → ('a','a'), ('a','b'), ('a','c'), ('b','b'), ('b','c'), ('c','c') 
  
    # nombre d'éléments de l'ensemble 
    n = len(elements) 
  
    # initialisation de la liste d'indices correspondant à une k-combinaison : [0, 0, .., 0] → ('a', 'a', .., 'a') 
    indices = [0] * k 
  
    # On génère la 1re combinaison. ex. : [0, 0, 0] → ('a', 'a', 'a') 
    yield tuple(elements[i] for i in indices) 
  
    while True: 
  
        # parcours des indices de la liste indices 
        for i in reversed(range(k)): 
            # Si la valeur de l'indice est différente de n-1 
            if indices[i] != n - 1: 
                break # On sort de la boucle : indice trouvé 
        else: 
            return 
  
        # copie (k-i) fois la valeur (indices[i] + 1) à partir de l'indice i dans la liste 
        indices[i:] = [indices[i] + 1] * (k - i) 
  
        # On génère la combinaison correspondant aux indices. 
        yield tuple(elements[i] for i in indices) 
  
  
print("Génération des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments..\n") 
  
# valeur de k 
k = 4 
  
print("k = " + str(k)) 
  
# création de la liste d'éléments 
elements = ['a','b','c'] 
  
print("E = " + str(elements).replace("[","{").replace("]","}")) 
  
print() 
  
print("I. Version n°1 : méthode classique\n") 
  
# Génère la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. 
combinaisons = generer_combinaisons(elements, k) 
  
print("Liste des combinaisons avec répétition :\n") 
  
# Affiche la liste des combinaisons 
print(combinaisons) 
  
print();print() 
  
print("II. Version n°2 : fonction génératrice avec yield\n") 
  
# Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments. 
gen_combinaisons = generateur_combinaisons(elements, k) 
  
print("Liste des combinaisons avec répétition :\n") 
  
# Affiche les combinaisons une à une. 
for combinaison in gen_combinaisons: 
    print(combinaison) 
  
print();print() 
  
print("III. Application : génération des triplets (x, y, z) tels que x + y + z = 4\n") 
  
# valeur de k 
k = 4 
  
print("k = " + str(k)) 
  
# création de la liste d'éléments 
elements = ['X', 'Y', 'Z'] 
  
print("E = " + str(elements).replace("[","{").replace("]","}")) 
  
print() 
  
# Crée le générateur permettant de parcourir la liste des combinaisons avec répétition de k éléments pris dans un ensemble de n éléments 
gen_combinaisons = generateur_combinaisons(elements, k) 
  
print("Liste des combinaisons et leur triplet (x, y, z) tel que x + y + z = 4 :\n") 
  
# Affiche les triplets (x, y, z) tels que x + y + z = 4 
for combinaison in gen_combinaisons: 
    # détermination du nombre de 'X', de 'Y' et de 'Z' pour chaque combinaison 
    x, y, z = combinaison.count("X"), combinaison.count("Y"), combinaison.count("Z") 
  
    # Affiche la combinaison et son triplet (x, y, z). 
    print(str(combinaison) + " → " + str((x, y, z)))

V. Conclusion

Apr�s avoir d�crit bri�vement l'algorithme permettant d'obtenir la liste des combinaisons avec r�p�tition, on a pu proposer une premi�re fonction en Python bas�e sur cet algorithme.

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/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combinatoire
https://docs.python.org/fr/3/library/itertools.html
https://gayerie.dev/docs/python/pyth...es-generateurs
https://www.mathraining.be/chapters/35?type=1&which=118

Vous avez lu gratuitement 0 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer � vous proposer des publications.

Une erreur dans cette actualit� ? Signalez-nous-la !

Votre nom : Votre e-mail :

D�crivez l'erreur que vous souhaitez porter � notre connaissance :

Identifiez-vous

Cr�er un compte

Analyse combinatoire et Python : les combinaisons avec r�p�tition

Un billet blog de Denis Hulo

Identifiant
Mot de passe

Mot de passe oubli� ?

Identifiez-vous

Cr�er un compte

Analyse combinatoire et Python : les combinaisons avec r�p�tition Un billet blog de Denis Hulo

Analyse combinatoire et Python : les combinaisons avec r�p�tition

Un billet blog de Denis Hulo