User

[Actualit�] Analyse combinatoire et Python : g�n�rer des arrangements par r�cursivit�

par

User

, 17/04/2024 � 10h25 (3910 Affichages)

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 :

Nom : arrangements.png
Affichages : 11448
Taille : 4,8 Ko

Nom : arrangements.png
Affichages : 11448
Taille : 4,8 Ko

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 :

Nom : arbre_arrangements.png
Affichages : 2667
Taille : 89,6 Ko

Nom : arbre_arrangements.png
Affichages : 2667
Taille : 89,6 Ko

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)