IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Analyse combinatoire et Python : les combinaisons avec répétition

Noter ce billet
par , 03/04/2024 à 15h27 (5155 Affichages)
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 :

Nom : nombre_combinaisons.png
Affichages : 9365
Taille : 2,6 Ko

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 (i0, i1, i2, i3) (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 (i0, i1, i2, i3) 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 i0 ≤ i1 ≤ i2 ≤ i3 ≤ 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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 3 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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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

Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Viadeo Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Twitter Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Google Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Facebook Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Digg Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Delicious Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog MySpace Envoyer le billet « Analyse combinatoire et Python : les combinaisons avec répétition » dans le blog Yahoo

Mis à jour 02/10/2024 à 14h02 par User

Catégories
Programmation , Python , Algorithmique

Commentaires

  1. Avatar de Fadelion
    • |
    • permalink
    Bonjour, très instructif ce billet de blog. Merci à vous pour cet article.
    J'aimerais souligner une petite erreur de frappe au niveau de l'équation avec x, y et z. Il y a eu une répétition du y dans la notation.
    Merci bien à vous
  2. Avatar de User
    • |
    • permalink
    Merci à vous pour ce message, je corrige la coquille