Permutation (informatique)

En programmation informatique, une permutation consiste à intervertir les valeurs de deux variables. Il s'agit d'une opération courante, mais rarement intégrée aux langages de programmation et jeu d'instructions des processeurs.

De nombreux algorithmes, en particulier des algorithmes de tri, utilisent des permutations.

Algorithmes

En utilisant une variable temporaire

La méthode la plus simple et probablement la plus répandue pour permuter deux variables est d'utiliser une troisième variable temporaire. C'est aussi la seule fiable sous réserve que les trois variables x, y et temp soient de même type (tous des entiers, tous des flottants, tous des caractères etc.).

Permutation de x et y:

temp = x
x = y
y = temp

L'inconvénient de cette méthode est qu'elle nécessite une variable supplémentaire. Cela n'a normalement pas d'importance si les variables ont un type élémentaire (entier, nombre flottant, etc), mais peut poser des problèmes pour des structures complexes occupant une grande quantité de mémoire (par exemple des tableaux).

En utilisant l'opération XOR

Lorsque deux variables sont représentées chacune sur un seul mot mémoire, il est possible de les permuter en utilisant la fonction OU exclusif bit à bit (XOR en anglais). Cette méthode ne nécessite pas de variable temporaire, mais nécessite l'existence de cette fonction dans le langage pour le type de donnée traité.

Permutation de x et y :

x = x XOR y
y = x XOR y
x = x XOR y

Cette méthode est fortement dépendante de la représentation des entiers en machine. Sur des flottants c'est différent, cela ne fonctionne pas non plus sur les caractères.

En utilisant l'addition et la soustraction

Une variante de la permutation par XOR est d'utiliser une addition et deux soustractions. Elle a l'inconvénient de poser des problèmes de dépassement sur les entiers et d'arrondis sur les flottants et de ne pas fonctionner sur les chaines de caractères par exemple.

Permutation de x et y :

x = x + y
y = x - y
x = x - y

Implantation en matériel

Certains processeurs disposent d'une instruction swap permettant de permuter deux registres. C'est le cas par exemple des processeurs x86 (instruction XCHG).

Sur les processeurs x86, l'instruction NOP consiste à permuter le registre eax avec lui-même.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Swap (computer science) » (voir la liste des auteurs).

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « XOR swap algorithm » (voir la liste des auteurs).