IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Algorithme itératif pour générer les arrangements de p éléments parmi n

Noter ce billet
par , 19/08/2021 à 10h18 (6210 Affichages)
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 :

(i0,i1,i2) avec i0≠i1, i0≠i2 et i1≠i2

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

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


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

Nom : arrangements.png
Affichages : 1576
Taille : 63,1 Ko

ij,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 :

(ij,0, ij,1,.., ij,k-1, ij,k, ij,k+1,.., ij,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 1er indice ij,k en partant de la droite qui puisse être incrémenté tout en restant différent des indices qui le précèdent (ij,0, ij,1,.., ij,k-1).

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

(ij,0, ij,1,.., ij,k-1, ij+1,k, ij+1,k+1,.., ij+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 ij+1,k après avoir incrémenté ij,k.
ij+1,k étant le plus petit indice supérieur à ij,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 :

  • ij+1,k+1 est le plus petit indice supérieur ou égal à 0 et différent des indices qui le précèdent.
  • ij+1,k+2 est le plus petit indice supérieur à ij+1,k+1 et différent des indices qui le précèdent.
  • ij+1,k+3 est le plus petit indice supérieur à ij+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.

Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Viadeo Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Twitter Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Google Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Facebook Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Digg Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Delicious Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog MySpace Envoyer le billet « Algorithme itératif pour générer les arrangements de p éléments parmi n » dans le blog Yahoo

Mis à jour 20/08/2021 à 17h35 par User

Catégories
Programmation , Python

Commentaires