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

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