En informatique, il est une opération courante de vouloir permuter deux variables, et même si certain langage implémente cette fonctionnalité en leur sein (Python par exemple), on voit souvent les programmeurs et programmeuses recoder la permutation.
Permutation classique avec variables temporaires
Si nous devions imaginer une implémentation de la permutation, la première qui nous vient à l’esprit est surement celle-ci.
Imaginons que nous ayons 2 melons en mains, un melon vert dans la main droite et un melon jaune dans la main gauche, j’aimerais échanger de mains mes melons. Malheureusement les melons sont trop lourds et je ne peux qu’en mettre un dans chaque main. La meilleure solution, et vous en conviendrez que c’est celle que vous utiliseriez dans ce cas, consiste (1) à poser un des melons sur une table ce qui permet de libérer une main, (2) de changer de main le melon qui n’a pas été posé, et (3) de finalement reprendre le melon posé avec l’autre main. Ça se passe donc en 3 temps.
Prenons les variables a et b que nous voulons permuter.
Le pseudo-code suivant permet de permuter nos variables.
a = 5
b = 3
temp = a
a = b
b = temp
La variable temp est une variable dite temporaire, dans le sens où elle n’est utilisée que pour permettre la permutation, comme la table dans mon analogie fruitière. Elle permet de garder l’information comme on peut le voir dans le dérouler de l’exécution ci-dessous :
| Ligne | a | b | temp |
|---|---|---|---|
| 2 | 5 | 3 | 0 |
| 3 | 5 | 3 | 5 |
| 4 | 3 | 3 | 5 |
| 5 | 3 | 5 | 5 |
Mais le titre de ce billet c’est "sans variable temporaire". Or là, on en utilise une.
Tous doux ! Effectivement, et j’y viens, on peut permuter sans variable temporaire. En fait on peut le faire d’au moins deux façons en utilisant des propriétés mathématiques.
Permutation SANS variable temporaire
Bon on y est, deux façons donc !
On peut faire une permutation sans variable temporaire avec la propriété de deux opérations.
L’opération de l’addition (et soustraction)
La propriété intéressante de l’addition est la suivante.
Bon avec seulement ça, ce n’est pas sûr que vous voyez où nous allons, alors je vais éclaircir un peu.
peut nous servir de variable temporaire.
Soit l’algorithme suivant :
a = 3
b = 5
a = a + b
b = a - b
a = a - b
On remarque qu’il n’y a pas de variable temporaire. Mais la permutation est-elle bien effective ? Pour s’en convaincre, écrivons l’exécution de l’algorithme avec les variables indicées de leur valeur au ième temps.
| Ligne | a | b |
|---|---|---|
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | b₀ | a₀ |
À la fin, on a bien et . La permutation est bien effective.
Cette méthode peut poser problème selon la taille des objets a et b. Les nombres entiers étant bornés dans leur implémentation, cette borne peut etre dépassé à l’addition de a et b, ce qui causera un bug de l’algorithme.
L’opération XOR
keuwa ?
XOR est une opération binaire dite "bits à bits" appelés aussi le ou exclusif dont la valeur renvoie 1 quand les 2 bits sont différents. Sa table de vérité est :
| p | q | p XOR q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Ainsi
La propriété intéressante de XOR qu’on va utiliser est que :
ce qui peut se montrer facilement avec une table de vérité.
| p | q | p XOR q | (p XOR q) XOR q |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
La première et la quatrième colonnes sont égales.
et aussi de manière plus anecdotique que
Soit l’algorithme suivant :
a = 0011
b = 1001
a = a XOR b
b = a XOR b
a = a XOR b
À la fin de cet algorithme, on a
et
On a bien la permutation qui a été effectué.
Cependant cela nécessite l’existence d’une fonction XOR pour les types utilisés.
La permutation est simple, mais parfois c’est dans les choses simples, qu’on se casse le plus la tête.
Merci pour votre lecture.
On pourrait arguer que la pile est un "temporaire" de plus mais comme elle est omniprésente dans la VM Python, ça me semble encore une fois se tromper de cible.