Enumérer les Permutations

1. Déterminer toutes les permutations

Les permutations sont les façons d'arranger des éléments dans une liste. Par exemple, si on a trois places sur un canapé et que trois personnes s'y assoient, les permutations représentent toutes les configurations possibles.
C'est-à-dire : [ABC], [CBA], [BAC], [CAB], [ACB] et [BCA].

Pourvoir énumérer toutes les permutations est intéressant. Supposons qu'on arrive en bas de l'immeuble d'un ami et qu'on a oublié les 4 chiffres de son digicode. En bon détective, on commence par repérer les touches les plus usées ou avec le plus de traces de doigts. Ca nous donne les 4 chiffres, mais pas dans quel ordre il faut les taper.
Si on a un algorithme pour énumérer toutes les permutations de 4 chiffres, on n'a que 24 combinaisons à tester.

Dans cet article, nous allons étudier deux algorithmes pour lister toutes les permutations de n éléments. Le premier génère toute la liste avant de rendre la main. Tandis que le second retourne la permutation qui suit celle qu'on lui passe en argument.

Essayez votre propre technique avec la grille suivante. Il s'agit d'afficher les 24 permutations de 4 lettres (A, B, C et D). Un click sur une case vide ajoute la lettre suivante. Un click sur la dernière lettre ajoutée la supprime.

2. Algorithme récursif

def make(size, result=[], level=0, item=None):
    if level >= size:
        result.append(item[:])
        return
    if item == None:
        item = [-1 for i in range(size)]
    for index in range(size):
        if item[index] < 0:
            item[index] = level
            make(size, result, level + 1, item)
            item[index] = -1
    return result

Pour trouver toutes les permutations de n éléments, il suffit de considérer les cas où le premier élément est en première position, puis en deuxième, puis en troisième, ... et enfin en dernière position.

On a donc n cas de figure et pour chacun d'eux on se retrouve avec encore n - 1 éléments à permuter. On réitère donc le procédé jusqu'à ce qu'il ne reste plus d'élément à placer.

3. Algorithme successif

L'algorithme précédent (c'est-à-dire l'algorithme récursif) nous retourne une liste de toutes les permutations et nous apprend, au passage, comment les compter en fonction de n. Mais dans les cas où n est grand, la liste peut devenir plutôt longue. Par exemple : 4! = 24, 5! = 120, 10! = 3628800, 30! = 265252859812191058636308480000000.

Si on n'a pas la place de stocker de telles listes de permutations, où que l'on veut juste essayer des combinaisons de coffre fort les unes après les autres jusqu'à trouver la bonne, il vaut mieux utiliser un algorithme qui, à partir d'une permutation quelconque, nous retourne la suivante.

Pour cela, on doit considérer chaque permutation comme un nombre à n chiffres. Et on doit donner un ordre aux éléments utilisés.

Par exemple, si on cherche les permutations de 5 lettres, on se munit de l'ordre alphabétique et on déclare que A < B < C < D < E. ON peut alors considérer que ABCDE est le plus petit nombre que l'on peut écrire avec ces 5 lettres et EDCBA le plus grand.

Recherchons, par exemple, le successeur de ACEDB.

On remarque que les trois derniers chiffres sont en ordre décroissant. Ce qui signifie que la valeur de ce triplet est maximale. En effet, n'importe laquelle des 5 autrs permutations de ces trois lettres donnerait un nombre plus petit.

En revanche, la lettre C est plus petite que sa voisine de droite. Alors si on la remplace par une lettre supérieure, on aura un plus grand nombre. Or, comme on cherche le plus petit des nombres supérieurs, on va choisir de le remplacer par la lettre D (l'autre choix aurait été E).

La permutation suivante va donc ressemble à ceci : AD..... Les lettres qui restent sont C, E et B. Si on veut minimiser la valeur du nombre qu'ils forment, il faut les ranger par ordre croissant. On obtient donc : ADBCE.

Voici à quoi cela ressemble en Python :

def Next(perm):
    idxEnd = len(perm) - 1
    last = perm[idxEnd]
    idxCur = idxEnd - 1
    while idxCur > -1:
        val = perm[idxCur]
        if val < last:
            break
        last = val
        idxCur -= 1
    if idxCur < 0:
        return None
    out = perm[:idxCur]
    idxPivot = idxCur
    idxCur += 1
    while idxCur <= idxEnd and perm[idxCur] > val:
        idxCur += 1
    idxFirst = idxCur - 1
    out.append(perm[idxFirst])
    idxCur = idxEnd
    while idxCur > idxPivot:
        if idxCur == idxFirst:
            out.append(val)
        else:
            out.append(perm[idxCur])
        idxCur -= 1
    return out

Cet algorithme s'arrête quand la liste est triée par ordre décroissant et il commence par une liste triée par ordre croissant. Ainsi, on ignore la fin de la liste si elle est déjà triée par ordre décroissant. Ainsi, si on a [3, 5, 4, 2, 1, 0], on ne s'occuppe que de la sous-liste [3, 5, 4].