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

D'après Wikipedia, en analyse combinatoireanalyse combinatoire, les combinaisons sans répétitionanalyse combinatoire 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₀, i₁, i₂) (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₀, 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₂.

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

D'après Wikipedia, en analyse combinatoireanalyse combinatoire, une combinaison avec répétitionanalyse combinatoire 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₀, 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₃.

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

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₀, i₁, i₂) 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₀, 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₂.

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

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

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