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 combinaisons de p éléments parmi n

Noter ce billet
par , 26/07/2021 à 11h19 (6839 Affichages)
I. Introduction

L'ensemble des combinaisons de p éléments parmi n peut-être généré en utilisant des fonctions récursives.

Malheureusement ces fonctions ont besoin de plus d'espace mémoire que les fonctions itératives, ce qui peut augmenter nettement le temps d'exécution dans le cas d'un grand nombre d'appels récursifs. C'est pourquoi il vaut mieux en général choisir d'implémenter un algorithme itératif pour ce type de problème.

L'objectif de ce billet est surtout 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 combinaisons

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

(0,1,2,3,4,5)

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

Et si maintenant on choisit par exemple les 3 premières boules, on obtient une combinaison sous forme de tuple, contenant leurs indices respectifs :

(0,1,2)

En effet, choisir (0,1,2) équivaut à 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<i2

On gardera donc uniquement les dispositions telles que i0<i1<i2.


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

Nom : combinaisons.png
Affichages : 12061
Taille : 30,7 Ko

Donc, dans le cas général une combinaison de p boules parmi n peut s'écrire sous forme de tuple :

(i0, i1,.., ik,.., ip-1) avec i0<i1<..<ik<..<ip-1.

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

On cherchera donc le 1er indice en partant de la droite qui respecte la condition k <= ik < k+(n-p) et qui puisse donc être incrémenté de 1:

ik -> ik+1.

Sans oublier bien sûr de recaler aussi les numéros des boules suivantes en faisant en sorte qu'ils respectent une progression arithmétique de raison 1:

(i0,i1,..,ik+1,ik+2,..,ik+(p-k)) avec i0<i1<..<ik+1<..<ik+(p-k).

Toutes les combinaisons d'indices qui ne respectent pas ces règles seront donc ignorées au cours de la procédure.


III. Fonctions itératives en Python

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
def combinaisons_v1(p,n):
    liste_combinaisons=[] # initialisation de la liste des combinaisons à générer    
    indices=list(range(p)) # initialisation de la liste avec les indices de départ [0,1,...,p-1]
 
    liste_combinaisons.append(tuple(indices)) # conversion de la liste des indices en tuple puis ajout à la liste des combinaisons
 
    if p==n:
        return liste_combinaisons
 
    i = p-1 # on commence à incrémenter le dernier indice de la liste
 
    while (i != -1): # tant qu'il reste encore des indices à incrémenter
 
        indices[i] += 1 # on incrémente l'indice
 
        for j in range(i + 1, p): # on recale les indices des éléments suivants par rapport à ndices[i]
            indices[j] = indices[j - 1] + 1           
 
        if indices[i] == (n  - p + i): # si cet indice a atteint sa valeur maxi
            i -= 1 # on repère l'indice précédent
        else: # sinon
            i = p - 1 # on repère le dernier indice
 
        liste_combinaisons.append(tuple(indices)) # ajout de la combinaison à la liste
 
    return liste_combinaisons

Cette fonction peut certainement être améliorée.

combinaisons(20,25).

Une version pour générer des combinaisons 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
def combinaisons_v2(p,e):
    liste_combinaisons=[] # initialisation de la liste des combinaisons à générer
    n=len(e) # dimension de l'ensemble
 
    indices=list(range(p)) # initialisation de la liste avec les indices de départ [0,1,...,p-1]
 
    liste_combinaisons.append(tuple([e[index] for index in indices])) # ajout de la combinaison à la liste
 
    if p==n:
        return liste_combinaisons
 
    i = p-1  # on commence à incrémenter le dernier indice de la liste
 
    while (i != -1): # tant qu'il reste encore des indices à incrémenter
 
        indices[i] += 1 # on incrémente l'indice
 
        for j in range(i + 1, p): # on recale les indices des éléments suivants par rapport à ndices[i]
            indices[j] = indices[j - 1] + 1           
 
        if indices[i] == (n  - p + i): # si cet indice a atteint sa valeur maxi
            i = i - 1 # on repère l'indice précédent
        else: # sinon
            i = p - 1 # on repère le dernier indice
 
        liste_combinaisons.append(tuple([e[index] for index in indices])) # ajout de la combinaison à la liste
 
    return liste_combinaisons

combinaisons_v2(3,['a','b','c','d','e']).

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 chacune des combinaisons 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 combinaisons de p éléments parmi n.

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

Mis à jour 07/07/2022 à 14h58 par User

Catégories
Programmation , Python