Générer des combinaisons et des arrangements par incrémentation d'indices

Denis Hulo

Objectif : générer des combinaisons et des arrangements en utilisant des algorithmes itératifs.

Niveau requis : confirmé

Commentez cet article : Commentez

- Titre : Générer des combinaisons et des arrangements par incrémentation d'indices

- Auteur : Denis Hulo

- Parution : 19 mars 2025

- Public visé :

- Licence : Copyright ® 2025 Denis Hulo. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Algorithmes itératifs

- II-A. Combinaisons sans répétition

- II-B. Combinaisons avec répétition

- II-C. Arrrangements

- III. Implémentation en Python

- III-A. Combinaisons sans répétition

- III-B. Combinaisons avec répétition

- IV. Conclusion

- V. Téléchargement

- VI. Remerciements

I - Introduction

Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même. On oppose généralement les algorithmes récursifs aux algorithmes itératifs, qui eux, utilisent plutôt des boucles pour et des boucles tant que, pour répéter des opérations.

L'objectif sera cette fois de créer des fonctions en Python qui pourront générer la liste des combinaisons avec et sans répétition de k éléments pris dans un ensemble de n éléments.

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

II - Algorithmes itératifs

Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même. On oppose généralement les algorithmes récursifs aux algorithmes itératifs, qui eux, utilisent plutôt des boucles pour et des boucles tant que, pour répéter des opérations.

Dans notre cas, on va utiliser des algorithmes itératifs pour générer des combinaisons et des arrangements par incrémentation d'indices.

II-A - Combinaisons sans répétition

D'après Wikipedia, en analyse combinatoire, les combinaisons sans répétition sont un concept de mathématiques, plus précisément de combinatoire, décrivant les différentes façons de choisir un nombre donné d'objets dans un ensemble de taille donnée, lorsque les objets sont discernables et que l'on ne se soucie pas de l'ordre dans lequel les objets sont placés ou énumérés. Le nom complet, bien que peu usité est combinaison sans répétition de n éléments pris k à k. Autrement dit, les combinaisons de taille k d'un ensemble E de cardinal n sont les sous-ensembles de E qui ont pour taille k.

Prenons par exemple un ensemble de n=5 éléments : E = {a, b, c, d, e}.

On souhaite obtenir la liste des combinaisons de k=3 éléments pris sans remise dans l'ensemble E, c'est-à-dire générer la liste des 10 combinaisons sans répétition :

(a, b, c), (a, b, d), ..., (c, d, e).

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

(a, b, c, d, e) → (0, 1, 2, 3, 4).

On génère ensuite les 3-uplets ou triplets d'indices (i_0, i_1, i_2) (croissants au sens strict) et leur combinaison, du premier (0, 1, 2) au dernier (2, 3, 4), dans cet ordre :

(0, 1, 2) → (a, b, c)
(0, 1, 3) → (a, b, d)
(0, 1, 4) → (a, b, e)
(0, 2, 3) → (a, c, d)
(0, 2, 4) → (a, c, e)
(0, 3, 4) → (a, d, e)
(1, 2, 3) → (b, c, d)
(1, 2, 4) → (b, c, e)
(1, 3, 4) → (b, d, e)
(2, 3, 4) → (c, d, e)

On incrémente donc à chaque fois les indices des k-uplets (i_0, i_1, i_2) 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_0 ≤ i_1 ≤ 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).

II-B - 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.

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_0, i_1, i_2, i_3) (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_0, i_1, i_2, i_3) 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_0 ≤ i_1 ≤ i_2 ≤ i_3.

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).

II-C - Arrrangements

Prenons par exemple un ensemble de n=4 éléments : E = {a, b, c, d}.

On souhaite obtenir la liste des arrangements de k=3 éléments pris dans l'ensemble E, c'est-à-dire générer la liste des 24 arrangements :

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

On va une nouvelle fois associer à chaque élément de cet ensemble un indice débutant à 0 comme en Python :

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

Il faut également avant chaque génération de k-uplet enregistrer la lste des indices accupées :

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

0: indice pris, 1: indice libre.

On génère ensuite les 3-uplets ou triplets d'indices (i_0, i_1, i_2) et leur arrangement, du premier (0, 1, 2) au dernier (3, 2, 1), dans cet ordre :

(0, 1, 2) → (a, b, c) ------------ (0, 1, 2, 3) ------ (3, 2, 1)
(0, 1, 3) → (a, b, d) ------------ (1, 1, 0, 1)
(0, 2, 1) → (a, c, b) ------------ (1, 1, 1, 0)
(0, 2, 3) → (a, c, d) ------------ (1, 0, 1, 1)
(0, 3, 1) → (a, d, b) ------------ (1, 1, 0, 1)
(0, 3, 2) → (a, d, c) ------------ (1, 0, 1, 1)
(1, 0, 2) → (b, a, c) ------------ (1, 1, 1, 0)
(1, 0, 3) → (b, a, d) ------------ (1, 1, 0, 1)
(1, 2, 0) → (b, c, a) ------------ (1, 1, 1, 0)

On incrémente donc à chaque fois les indices des k-uplets (i_0, i_1, i_2) 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_0 ≤ i_1 ≤ 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).

Loi binomiale

III - Implémentation en Python

III-A - Combinaisons sans répétition

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

def generer_combinaisons(elements, k):
# fonction permettant de générer la liste des combinaisons sans répétition de k éléments pris dans un ensemble de n éléments
# generer_combinaisons(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','c')

# nombre d'éléments de l'ensemble
n = len(elements)

# initialisation de la liste d'indices correspondant à une k-combinaison : [0, 1, 2] → ('a', 'b', 'c')
indices = list(range(k))

# On crée la 1re combinaison à partir de la liste d'indices. ex. : [0, 1, 2] → ('a', 'b', 'c')
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 i + n - k.
if indices[i] != i + n - k:
break # On sort de la boucle : indice trouvé
else: # sinon
break # On sort de la boucle.

# incrémentation du 1er indice le permettant à droite
indices[i] += 1

# oon recalle les indices à droite. ex. pour i=1 : [0, 1, 3, 4] -> [0, 2, 3, 4]
for j in range(i+1, k):
indices[j] = indices[j-1] + 1

# 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 présentée dans la documentation du module itertools.

Testons maintenant la fonction :

# 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')]

III-B - 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 :

def generer_combinaisons_repetition(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 :

# 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 - Conclusion

V - Téléchargement

Le fichier compressé contenant le module Python pour effectuer les différents tests.

VI - Remerciements

Je tiens à remercier ... pour le suivi de cet article, ainsi que ... pour sa relecture.

Sources

- Page Wikipedia sur les combinaisons sans répétition

- Page Wikipedia sur les combinaisons avec répétition

- Page Wikipedia sur les arrangements