User

I. Introduction

Après les combinaisons, on s'intéresse maintenant aux arrangements :

L'objectif sera cette fois de créer une fonction récursive en Python qui pourra générer la liste des arrangements de k éléments pris dans un ensemble à n éléments.

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



II. Arrangements

D'après Wikipedia, en analyse combinatoire, le nombre d'arrangements, défini pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, est le nombre de parties ordonnées de k éléments dans un ensemble de n éléments.

Lorsque l'on choisit k objets parmi n objets et que l’ordre dans lequel les objets sont sélectionnés revêt une importance, on peut les représenter par un k-uplet d'éléments distincts et on en constitue une liste ordonnée sans répétition possible, c'est-à-dire dans laquelle l'ordre des éléments est pris en compte (si l'on permute deux éléments de la liste, on a une liste différente, et un élément ne peut être présent qu'une seule fois). Une telle liste ordonnée est un arrangement.

Par exemple, au tiercé, il faut deviner l'ordre d'arrivée des 3 premiers chevaux parmi n au départ. Il y a alors autant de tiercés possibles à l'arrivée que d'arrangements de k=3 éléments pris parmi n.

Autre exemple, dans une assemblée de 30 personnes on doit élire un bureau composé de 4 membres (un président, un vice-président, un secrétaire et un trésorier). Il y a alors autant de bureaux possibles que d'arrangements de 4 éléments pris parmi 30.

Le nombre d'arrangements de k éléments pris dans un ensemble à n éléments est donné par les formules :



On peut remarquer que ce nombre croit rapidement quand k et n augmentent.



III. Génération des arrangements

Prenons par exemple un ensemble à n=4 éléments :

E = {a, b, c, d}

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

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


On peut dénombrer tous les résultats possibles à l'aide d'un arbre des possibilités :



On a 4 choix possibles (ou branches) au premier niveau, puis 3 choix possibles pour chaque nœud au second niveau, et enfin plus que 2 pour chaque nœud au dernier niveau, ce qui fait donc bien 4×3×2=24 triplets à la fin.


Cet arbre de dénombrement nous permet également de mieux visualiser le processus récursif de génération des arrangements.

Si on voulait par exemple afficher tous les arrangements de k éléments pris dans une liste donnée, on obtiendrait ainsi le pseudo-code récursif :

Code :

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
Algo arrangements(elements, k, arr=()):
    Si k=0 alors
        afficher(arr)
    Sinon
        Pour i de 0 jusqu'à longueur(elements)-1
            # nouvelle liste d'éléments sans elements[i] (indice débutant à 0 : comme en Python)
	    new_elements = elements[0:i] + elements[i+1:]

            # nouveau tuple avec elements[i] en plus
	    new_arr = arr + elements[i]

            # appel récursif pour k-1
            arrangements(new_elements, k-1, new_arr) 
	Fin pour
    Fin si   
Fin Algo

On va maintenant se baser sur cet algorithme pour écrire nos fonctions en Python.



IV. Implémentation en Python


IV-A. Génération des arrangements

On présente maintenant la fonction récursive qui génère la liste contenant les arrangements de k éléments pris dans un ensemble à 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
def generer_arrangements(elements, k, arr=()):
    # fonction permettant de générer la liste des arrangements de k éléments pris dans un ensemble de n éléments
    # generer_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b')
 
    # si k=0
    if k==0:
        # On renvoie une liste contenant l'arrangement arr. 
        return [arr]
 
    else: # sinon
        # initialisation de la liste des arrangements
        arrangements = []
 
        # parcours des éléments et de leur indice
        for i,e in enumerate(elements):
            # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))
            # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr 
            arrangements += generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))
 
        # Renvoie la liste des arrangements.
        return arrangements

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 = 3
 
# création de la liste d'éléments
elements = ['a','b','c','d']
 
# Génère la liste des arrangements de k éléments pris dans un ensemble de n éléments.
arrangements = generer_arrangements(elements, k)
 
# Affiche la liste des arrangements.
print(arrangements)

Le code affiche :

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



IV-B. Fonction génératrice avec yield et yield from

Comme on l'a vu précédemment, le nombre d'arrangements 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 des instructions yield et yield from qui permettent de transformer la fonction récursive 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
def generateur_arrangements(elements, k, arr=()):
    # fonction permettant de générer tous les arrangements de k éléments pris dans un ensemble de n éléments
    # generateur_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b')
 
    # si k=0 
    if k==0:
        # On génère l'arrangement arr. 
        yield arr
 
    else: # sinon
        # parcours des éléments et de leur indice
        for i,e in enumerate(elements):
            # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) : yield from ..
            # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr 
            yield from generateur_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))

Comme on peut le constater, on utilise l'instruction yield from juste avant l'appel récursif et l'instruction yield pour générer l'arrangement.

L'instruction yield from, apparue avec la version 3.3 de Python, autorise le générateur à déléguer une partie de ses opérations à un autre générateur.

Testons maintenant notre fonction :

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
# valeur de k
k = 3
 
# création de la liste d'éléments
elements = ['a','b','c','d']
 
# Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments.
gen_arrangements = generateur_arrangements(elements, k)
 
print("Liste des arrangements :\n")
 
# parcours des arrangements un à un
for arrangement in gen_arrangements:
    # Affiche l'arrangement.
    print(arrangement)

Le code affiche :

Liste des arrangements :

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

Vous pouvez d'ailleurs retrouver ce type de fonction dans la librairie itertools.


IV-C. Application : tiercés dans l'ordre

On a 4 chevaux au départ d'une course, numérotés de 1 à 4, et on souhaite obtenir tous les tiercés dans l'ordre possibles :

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
# valeur de k
k = 3
 
print("k = " + str(k))
 
# création de la liste d'éléments : numéros au départ
elements = [1, 2, 3, 4]
 
print("E = " + str(elements).replace("[","{").replace("]","}"))
 
print()
 
# Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments
gen_arrangements = generateur_arrangements(elements, k)
 
print("Liste des tiercés dans l'ordre possibles :\n")
 
# parcours les arrangements un à un : tiercés possibles
for arrangement in gen_arrangements:
    # Affiche l'arrangement : tiercé possible
    print(arrangement)

Le code affiche :

k = 3
E = {1, 2, 3, 4}

Liste des tiercés dans l'ordre possibles :

(1, 2, 3)
(1, 2, 4)
(1, 3, 2)
(1, 3, 4)
(1, 4, 2)
(1, 4, 3)
(2, 1, 3)
(2, 1, 4)
(2, 3, 1)
(2, 3, 4)
(2, 4, 1)
(2, 4, 3)
(3, 1, 2)
(3, 1, 4)
(3, 2, 1)
(3, 2, 4)
(3, 4, 1)
(3, 4, 2)
(4, 1, 2)
(4, 1, 3)
(4, 2, 1)
(4, 2, 3)
(4, 3, 1)
(4, 3, 2)


IV-D. Module complet

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

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
def generer_arrangements(elements, k, arr=()):
    # fonction permettant de générer la liste des arrangements de k éléments pris dans un ensemble de n éléments
    # generer_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b')
 
    # si k=0
    if k==0:
        # On renvoie une liste contenant l'arrangement arr. 
        return [arr]
 
    else: # sinon
        # initialisation de la liste des arrangements
        arrangements = []
 
        # parcours des éléments et de leur indice
        for i,e in enumerate(elements):
            # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))
            # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr 
            arrangements += generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))
 
        # Renvoie la liste des arrangements.
        return arrangements
 
 
def generateur_arrangements(elements, k, arr=()):
    # fonction permettant de générer tous les arrangements de k éléments pris dans un ensemble de n éléments
    # generateur_arrangements(['a','b','c'], 2) → ('a','b'), ('a','c'), ('b','a'), ('b','c'), ('c','a'), ('c','b')
 
    # si k=0 
    if k==0:
        # On génère l'arrangement arr.
        yield arr
 
    else: # sinon
        # parcours des éléments et de leur indice
        for i,e in enumerate(elements):
            # appel récursif pour k-1 : generer_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,)) : yield from ..
            # arguments : elements[0:i] + elements[i+1:] → elements, k-1 → k, arr + (e,) → arr  
            yield from generateur_arrangements(elements[0:i] + elements[i+1:], k-1, arr + (e,))    
 
 
print("Génération des arrangements de k éléments pris dans un ensemble de n éléments..\n")
 
# valeur de k
k = 3
 
print("k = " + str(k))
 
# création de la liste d'éléments
elements = ['a','b','c','d']
 
print("E = " + str(elements).replace("[","{").replace("]","}"))
 
print()
 
print("I. Version n°1 : fonction récursive classique\n")
 
# Génère la liste des arrangements de k éléments pris dans un ensemble de n éléments.
arrangements = generer_arrangements(elements, k)
 
print("Liste des arrangements :\n")
 
# Affiche la liste des arrangements
print(arrangements)
 
print();print()
 
print("II. Version n°2 : fonction génératrice avec yield et yield from\n")
 
# Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments.
gen_arrangements = generateur_arrangements(elements, k)
 
print("Liste des arrangements :\n")
 
# parcours des arrangements un à un
for arrangement in gen_arrangements:
    # Affiche l'arrangement.
    print(arrangement)
 
print();print()
 
print("III. Application : tiercés dans l'ordre\n")
 
# valeur de k
k = 3
 
print("k = " + str(k))
 
# création de la liste d'éléments : numéros au départ
elements = [1, 2, 3, 4]
 
print("E = " + str(elements).replace("[","{").replace("]","}"))
 
print()
 
# Crée le générateur permettant de parcourir la liste des arrangements de k éléments pris dans un ensemble de n éléments
gen_arrangements = generateur_arrangements(elements, k)
 
print("Liste des tiercés dans l'ordre possibles :\n")
 
# parcours les arrangements un à un : tiercés possibles
for arrangement in gen_arrangements:
    # Affiche l'arrangement : tiercé possible
    print(arrangement)

V. Conclusion

On a donc d'abord montré comment obtenir à l'aide d'un arbre de dénombrement tous les arrangements de 3 éléments pris dans un ensemble à 4 éléments. Puis, on a proposé une première fonction récursive en Python permettant de générer la liste des arrangements de k éléments pris parmi n.

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/Arrangement
https://fr.wikipedia.org/wiki/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Combinatoire
https://fr.wikipedia.org/wiki/Pseudo-code
https://gayerie.dev/docs/python/pyth...es-generateurs
https://docs.python.org/3/whatsnew/3.3.html#pep-380
http://villemin.gerard.free.fr/Puzzle/HazTierc.htm