User

I. Introduction

Après les combinaisons, on s'intéresse cette fois à un algorithme itératif pour générer tous les arrangements de p éléments parmi n.

Il va nous permettre ensuite d'implémenter une fonction en Python qui pourra générer un grand nombre d'arrangements sans avoir besoin de les stocker en mémoire.

L'objectif est toujours d'expliquer le fonctionnement de ce type d'algorithme sans trop s'attarder sur l'écriture de la fonction en Python.


II. Règles pour représenter et générer ces arrangements

Si on souhaite par exemple obtenir toutes les façons de tirer successivement 3 boules parmi 4 en tenant compte de l'ordre du tirage, il nous faut tout d'abord numéroter dans l'ordre les 4 boules de la manière suivante :

(0,1,2,3)

On fait commencer les indices des boules à 0 comme pour les indices des tuples en Python.

Et si maintenant on tire successivement les 3 premières boules dans l'ordre, on obtient un arrangement sous forme de tuple, contenant leurs indices respectifs :

(0,1,2)

Mais comme l'ordre du tirage est maintenant pris en compte, choisir (0,1,2) est différent de choisir (0,2,1) ou (1,0,2) ou (1,2,0) ou (2,0,1) ou (2,1,0).

On représentera alors le tirage de 3 boules quelconques par le tuple :

(i₀,i₁,i₂) avec i₀≠i₁, i₀≠i₂ et i₁≠i₂

On encore, si on souhaite indiquer qu'il s'agit de l'arrangement de rang j :

(i_j,0,i_j,1,i_j,2) avec i_j,0≠i_j,1, i_j,0≠i_j,2 et i_j,1≠i_j,2.


Tableau des arrangements et règles de passage entre 2 séquences d'indices successives :



i_j,k désignant l'indice k de l'arrangement j.

Dans le cas général, l'arrangement de la ligne j de p boules parmi n peut donc s'écrire sous forme de tuple :

(i_j,0, i_j,1,.., i_j,k-1, i_j,k, i_j,k+1,.., i_j,p-1) chaque indice étant unique (pas de doublon).

On aura alors des tirages qui s'étalent de (0,1,..,k,..,p-1) à ((n-1),(n-2),..,(n-k-1),..,n-p).

On cherchera donc le 1^er indice i_j,k en partant de la droite qui puisse être incrémenté tout en restant différent des indices qui le précèdent (i_j,0, i_j,1,.., i_j,k-1).

On obtient ensuite l'arrangement de la ligne j+1 représenté sous forme de tuple :

(i_j,0, i_j,1,.., i_j,k-1, i_j+1,k, i_j+1,k+1,.., i_j+1,p-1) chaque indice étant unique (pas de doublon).

Les k premiers indices ne changent pas par rapport au tuple précédent.

On obtient i_j+1,k après avoir incrémenté i_j,k.
i_j+1,k étant le plus petit indice supérieur à i_j,k et différent des indices qui le précèdent

Sans oublier bien sûr de réinitialiser aussi les indices suivants pour un prochain cycle :

• i_j+1,k+1 est le plus petit indice supérieur ou égal à 0 et différent des indices qui le précèdent.
• i_j+1,k+2 est le plus petit indice supérieur à i_j+1,k+1 et différent des indices qui le précèdent.
• i_j+1,k+3 est le plus petit indice supérieur à i_j+1,k+2 et différent des indices qui le précèdent.
• etc..

Toutes les séquences d'indices qui comportent des doublons seront donc ignorées au cours de la procédure.


III. Fonctions itératives en Python

Nous utilisons l'instruction yield qui permet de parcourir l'ensemble des arrangements, sans avoir besoin de les stocker en mémoire :

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
def arrangements_v1(p,n):
 
    if p>n: 
        return
 
    indices=list(range(p)) # on initialise la liste des indices [0,1,2,..,p-1]
    yield tuple(indices) # ordre pour générer le tuple 
 
    i=p-1 # on part de la fin de la liste des indices
    k=p # variable utilisé pour incrémenter ou initialiser les indices
 
    while i!=-1: # on parcourt les indices de la droite vers la gauche : p-1 -> 0
        if k < n: # si la valeur d'indice maxi n'a pas été dépassée
            if k not in indices[:i]: # si l'indice k n'est pas présent parmi les indices précédant indices[i]
                indices[i]=k # on incrémente indices[i] avec la valeur de k
                k=0;j=i+1 # on met k à 0 pour ensuite initialiser les prochains indices : nouveau cycle (ex. : 0,1,2,..).
                while (j < p): # on parcourt les prochains indices 
                    if k not in indices[:i+1]: # si l'indice k n'est pas présent parmi les indices précédant indices[i+1]
                        indices[j]=k # on initialise indices[j] avec la valeur de k
                        j+=1 # prochain indice
                    k+=1
                yield tuple(indices) # ordre pour générer le tuple
                i=p-1 # on revient sur le dernier indice à incrémenter 
                k=indices[i]
            k+=1 # on incrémente k
        else: # sinon
            i-=1 # on remonte les indices vers la gauche
            k=indices[i]+1 # on met à jour k pour le prochain indice
 
    return

Exemple de code permettant de générer les arrangements de 9 éléments parmi 14 :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
iterator = arrangements_v1(9,14)
 
# on génère les arrangements dans une boucle
for a in iterator: 
    # faire quelque chose avec l'arrangement a

Une version pour générer des arrangements de caractères alphanumériques :

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
def arrangements_v2(p,e):
 
    n=len(e) # longueur de la liste de caractères
 
    if p>n: 
        return
 
    indices=list(range(p)) # on initialise la liste des indices [0,1,2,..,p-1]
    yield tuple(e[i] for i in indices) # ordre pour générer le tuple 
 
    i=p-1 # on part de la fin de la liste des indices
    k=p # variable utilisé pour incrémenter ou initialiser les indices
 
    while i!=-1: # on parcourt les indices de la droite vers la gauche : p-1 -> 0
        if k < n: # si la valeur d'indice maxi n'a pas été dépassée
            if k not in indices[:i]: # si l'indice k n'est pas présent parmi les indices précédant indices[i]
                indices[i]=k # on incrémente indices[i] avec la valeur de k
                k=0;j=i+1 # on met k à 0 pour ensuite initialiser les prochains indices : nouveau cycle (ex. : 0,1,2,..).
                while (j < p): # on parcourt les prochains indices 
                    if k not in indices[:i+1]: # si l'indice k n'est pas présent parmi les indices précédant indices[i]
                        indices[j]=k # on initialise indices[j] avec la valeur de k
                        j+=1 # prochain indice
                    k+=1
                yield tuple(e[i] for i in indices) # ordre pour générer le tuple 
                i=p-1 # on revient sur le dernier indice à incrémenter 
                k=indices[i]
            k+=1 # on incrémente k
        else: # sinon
            i-=1 # on remonte les indices vers la gauche
            k=indices[i]+1 # on met à jour k pour le prochain indice
 
    return

Vous trouverez ce type de fonction dans la librairie itertools pour Python.

IV. Conclusion

Après avoir numéroté les n éléments d'un ensemble donné de 0 à n-1, nous avons pu représenter chacun des arrangements de p éléments pris dans cet ensemble à l'aide de séquences d'indices. Ceci nous a ensuite permis d'identifier certaines règles sur ces séquences. Finalement nous avons pu écrire la fonction permettant de générer dans l'ordre toutes les arrangements de p éléments parmi n.