Tutoriel Permutation algorithmique entière

[Creased]

Bonjour à tous, je viens tout juste de me remettre au C++, cela faisait très longtemps que je n'y avais pas touché et j'ai donc décidé de m'y remettre.

Pendant que je progresse au fil des chapitres de différents e-books, j'ai eu l'occasion de devoir implémenter un algorithme effectuant l'opération de la fameuse fonction de permutation. Après quelques tests, écritures de pseudos-codes sur brouillons et calculs binaires de plus en plus longs, j'ai réussi à trouver trois différents algorithmes qui seront facilement adaptables dans d'autres langages de programmation. Chacun de ces trois algorithmes présentent leurs avantages et inconvénients en terme de gestion de mémoire, temps processeur, adaptation, lisibilité et retranscription (et oui l'humain aussi doit de temps en temps bricoler par ses propres moyens en sortant un crayon et du papier) je vais donc vous les présenter un-à-un en vous exposant les éventuels inconvénients que j'ai pu constater.

Concept général de la permutation
La permutation algorithmique est une opération ciblant au moins deux variables et permet l'échange respectif des valeurs de ces variables. Voici un pseudo-code pour illustrer mes propos :

a <- 1;
b <- 5;

ECRIRE a, b; //!< a: 1
             //!< b: 5

PERMUT(a, b);

ECRIRE a, b; //!< a: 5
             //!< b: 1

Dans ce pseudo-code, on peut voir l'utilisation d'une fonction PERMUT dont le nom est bien entendu fictif, mais il s'agit de la fonction qui permet la permutation des valeurs respectives de a et b. Je vais donc vous montrer diverses méthodes permettant d'implémenter une telle fonction dans vos programmes.

Permutation par variable temporaire
Je commence par la plus rependue de toutes, celle que tous les programmeurs débutants étudient dans leurs débuts, la permutation exploitant une variable auxiliaire (ou temporaire):

#include <iostream>  //!< Flux d'entrée/sortie

/**
 * \brief Permutation de a et b exploitant une variable temporaire
 *
 * \author Creased
 */

int main() {
	//! Déclaration
	int a(2147483647), b(42);  //!< Variables à permuter
	int tmp;  //!< Variable temporaire

	//! Affichage prétraitement
	std::cout << "a: " << a << std::endl << "b: " << b << std::endl << "tmp: " << tmp << std::endl;  //!< a: 2147483647
	                                                                                                 //!< b: 42
	                                                                                                 //!< tmp: NULL

	//! Permutation

	tmp = a;  //!< a: 2147483647
	          //!< b: 42
	          //!< tmp: 2147483647

	a = b;    //!< a: 42
	          //!< b: 42
	          //!< tmp: 2147483647

	b = tmp;  //!< a: 42
	          //!< b: 2147483647
	          //!< tmp: 2147483647

	//! Affichage post-traitement
	std::cout << "a: " << a << std::endl << "b: " << b << std::endl << "tmp: " << tmp << std::endl;  //!< a: 42
	                                                                                                 //!< b: 2147483647
	                                                                                                 //!< tmp: 2147483647

	//! Fin du programme
    return 0;
}

Comme on peut le constater en ligne 34, les valeurs de a et b ont été respectivement interverties. Cette méthode fonctionne, mais met en avant son grand défaut à savoir l'utilisation d'une variable auxiliaire nécessaire au transfert des deux valeurs, imaginez-vous avec deux verres d'eaux de tailles identiques, transférer le contenue d'un verre à l'autre est chose aisée si l'on possède un troisième verre, mais ceci implique d'en posséder un de plus... C'est exactement la même chose avec les variables et donc les espaces mémoire, l'utilisation d'un espace mémoire supplémentaire est nécessaire et donc il faut être certain de sa disponibilité, pensez aux premiers développeurs sur Amiga avec leurs chipsets RAM de 256Ko, "Less is more.".

Son avantage est quant à lui indéniable, sa simplicité logique et sémantique.

Permutation arithmétique
Voici une méthode qui quant à elle n'exploite pas de troisième variable contenant une valeur auxiliaire pendant la permutation des valeurs des variables a et b , elle fait appel aux notions basiques de l'arithmétique élémentaire, la symétrie arithmétique (ou opposé arithmétique) :

#include <iostream>  //!< Flux d'entrée/sortie

/**
 * \brief Permutation de a et b exploitant une opération arithmétique
 *
 * \author Creased
 */

int main() {
    //! Déclaration
    int a(0x7fffffff), b(0x2a);  //!< Variables à permuter

    //! Affichage prétraitement
    std::cout << "a: " << a << std::endl << "b: " << b << std::endl;  //!< a: 2 147 483 647
                                                                      //!< b: 42

    //! Permutation

    a += b;     //!< a: (2 147 483 647) + (42)
                //!< a: (0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
                //!<   +(0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
                //!<    =========================================
                //!<     **** **** **** **** **** **** **** **
                //!<    =========================================
                //!<    (1000 0000 0000 0000 0000 0000 0010 1001): 0x80000029
                //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
                //!< a: -(2 147 483 607)
                //!< b: 42

    b = a - b;  //!< a: -(2 147 483 607)
                //!< b: -(2 147 483 607) - (42)
                //!< b: (1000 0000 0000 0000 0000 0000 0010 1001): 0x80000029
                //!<   -(0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
                //!<    (-a)-b=(-a)+(-b) donc:
                //!< b: (1000 0000 0000 0000 0000 0000 0010 1001): 0x80000029
                //!<   +(1111 1111 1111 1111 1111 1111 1101 0110): 0xffffffd6
                //!<    =========================================
                //!<   *
                //!<    =========================================
                //!<   1(0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
                //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
                //!<   ^ Débordement ...
                //!< b: 2 147 483 647


    a -= b;     //!< a: -(2 147 483 607) - (2 147 483 647)
                //!< a: (1000 0000 0000 0000 0000 0000 0010 1001): 0x80000029
                //!<   -(0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
                //!<    (-a)-b=(-a)+(-b) donc:
                //!< a: (1000 0000 0000 0000 0000 0000 0010 1001): 0x80000029
                //!<   +(1000 0000 0000 0000 0000 0000 0000 0001): 0x80000001
                //!<    =========================================
                //!<   *                                      *
                //!<    =========================================
                //!<   1(0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
                //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
                //!<   ^ Débordement ...
                //!< a: 42
                //!< b: 2 147 483 647

    //! Affichage post-traitement
    std::cout << "a: " << a << std::endl << "b: " << b << std::endl;  //!< a: 42
                                                                      //!< b: 2 147 483 647

    //! Fin du programme
    return 0;
}

Légendes et définitions :

• les symboles préfixés par '0x' sont les notations hexadécimales (base 16) des valeurs de a et b,
• les suites de 1 et 0 sont les notations binaires (base 2) des valeurs de a et b,
• les suites de '*' sont des retenues, je les ai mises afin que vous compreniez comment j'obtiens de tels résultats,
• le MSB (littéralement "Most Significant Bit"), la notation positionnelle du binaire veut que la valeur la plus à gauche soit la plus grande,
• Le LSB (littéralement "Least Significant Bit"), la notation positionnelle du binaire veut que la valeur la plus à droite soit la plus petite.

Ici l'utilisation d'opérateur arithmétique économise un espace mémoire, ceci permet donc par exemple dans les cas extrêmes, d'empêcher les temps d'attentes pour en libérer un ou l'utilisation de la mémoire swap (mémoire d'échange exploitant la mémoire de masse). Cependant, comme j'ai pu le décrire dans les commentaires du code, l'utilisation de ce type d'algorithme est risquée, car il peut provoquer ce que l'on appelle un débordement de mémoire ("memory overload/overflow"). Ce débordement de mémoire peut entraîner dans le pire des cas un plantage complet du programme ou la corruption des données traitées. Imaginez-vous développeur d'un programme de direction de drones à destination de la station spatiale internationale, la moindre erreur de ce genre pourrait compromettre des missions de ravitaillement, je vous laisse penser aux dommages collatéraux...

Ce débordement est dû tout simplement au fait qu'un entier signé codé sur 32 bits utilise un bit, le MSB, pour définir si l'entier est positif ou négatif, notez que si le MSB est à 0 le nombre est positif, or 0 (base 10) <-> 0 (base 2) donc 0 est positif et non neutre, la valeur max est donc :

((2^(32-MSB)) - 1) = 2 147 483 647 en base 10
soit (0111 1111 1111 1111 1111 1111 1111 1111) en base 2

La valeur minimale est donc égale à l'opposé de la valeur max + 1, car le 0 est positif soit :

((2 147 483 647) * (-1)) - 1 = (-2 147 483 648) en base 10
soit (1000 0000 0000 0000 0000 0000 0000 0000) en base 2

L'étendue d'un entier signé est donc de (-2 147 483 648) à (2 147 483 647).
Les entiers non-signés quant à eux n'utilisent pas le MSB pour savoir si un nombre est positif ou négatif, seuls les entiers positifs correspondent à un entier non-signé, leur étendue positive est donc plus grande et s'étend de 0 à ((2^32) - 1) soit (4 294 967 295).

Son avantage est donc l'absence de variable auxiliaire, mais son inconvénient majeur est le risque de débordement qu'il faut traiter dans tous les cas...

Permutation par disjonction exclusive
Pour finir voici le Saint Graal, cette méthode n'exploite pas de troisième variable, ne présente d'après mes tests, pas de risque de débordement. Elle fait appel à une notion très simple de la théorie de la logique combinatoire et séquentientielle mais aussi de l'algèbre de Boole, cette notion s'appelle le XOR (littéralement "OU exclusif" ou disjonction exclusive):

#include <iostream>  //!< Flux d'entrée/sortie

/**
 * \brief Permutation de a et b exploitant la disjonction exclusive de l'algèbre de Boole
 *
 * \author Creased
 */

int main() {
    //! Déclaration
    int a(0x7fffffff), b(0x2a);  //!< Variables à permuter

    //! Affichage prétraitement
    std::cout << "a: " << a << std::endl << "b: " << b << std::endl;  //!< a: 2 147 483 647
                                                                      //!< b: 42

    //! Permutation 'bitwise'

    /**
     * Table de vérité du XOR
     * | a | b | ^ |
     * | 1 | 1 | 0 |
     * | 1 | 0 | 1 |
     * | 0 | 1 | 1 |
     * | 0 | 0 | 0 |
     * le XOR vaut 1 lorsque seul a ou b vaut 1 et que ET(a, b) donne 1
     */

    a ^= b;  //!< a: (2 147 483 647) ^ (42)
             //!< a: (0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
             //!<   ^(0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
             //!<    =========================================
             //!<    (0111 1111 1111 1111 1111 1111 1101 0101): 0x7fffffd5
             //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
             //!< a: 2 147 483 605
             //!< b: 42

    b ^= a;  //!< a: 2 147 483 605
             //!< b: (42) ^ (2 147 483 605)
             //!< b: (0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
             //!<   ^(0111 1111 1111 1111 1111 1111 1101 0101): 0x7fffffd5
             //!<    =========================================
             //!<    (0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
             //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
             //!< b: 2 147 483 647

    a ^= b;  //!< a: (2 147 483 605) ^ (2 147 483 647)
             //!< a: (0111 1111 1111 1111 1111 1111 1101 0101): 0x7fffffd5
             //!<   ^(0111 1111 1111 1111 1111 1111 1111 1111): 0x7fffffff
             //!<    =========================================
             //!<    (0000 0000 0000 0000 0000 0000 0010 1010): 0x2a
             //!<     ^ Le MSB définit si l'entier signé est positif ou négatif
             //!< a: 42
             //!< b: 2 147 483 647

    //! Affichage post-traitement
    std::cout << "a: " << a << std::endl << "b: " << b << std::endl;  //!< a: 42
                                                                      //!< b: 2 147 483 647

    //! Fin du programme
    return 0;
}

Comme je vous l'ai dit, ceci est très simple, le plus dur à saisir si l'on n'est pas avertie est l'utilisation d'un "^=", il s'agit d'un opérateur bitwise (littéralement "bit-à-bit") dont vous connaissez sûrement déjà l'existence si vous utilisez ceux-ci :

• Addition bit-à-bit : +=
• Soustraction bit-à-bit : -=
• Multiplication bit-à-bit : *=
• Division bit-à-bit : /=

Son avantage est son efficacité, l'absence de risque de débordement, mais surtout l'absence de variable auxiliaire. Son inconvénient est sa lisibilité et dans une moindre mesure sa simplicité d'implémentation dans d'autres langages, en effet les bitwises ne sont pas présents dans tous les langages et il est possible qu'il soit nécessaire de procéder nous-mêmes à ce bouclage bit à bit. Voici un exemple d'algorithme sous forme de pseudo-code qui permet l'implémentation de cette méthode dans tous les langages de programmation, je ne vous épargne pas la recherche pour la syntaxe, car je ne suis pas un savant-fou qui maitrise tous les langages à la perfection (en toute honnêteté à ce stade de ma progression, je suis incapable de produire un code concis permettant son implémentation en C++ car il me manque des notions sur l'utilisation de chaînes binaires et à leurs parcours ) :

// SOUS-PROGRAMME: XOR
	// ARGUMENTS
		// ENTRÉE
			// a, b: entiers (bits du même rang dans le mot binaire (1 ou 0))
		// SORTIE
			// bln: booléen (bit résultant du XOR sous forme de booléen (true=1, false=0))
	// DEBUT
		/**
		 * Table de vérité du XOR
		 * | a | b | ^ |
		 * | 1 | 1 | 0 |
		 * | 1 | 0 | 1 |
		 * | 0 | 1 | 1 |
		 * | 0 | 0 | 0 |
		 * le XOR vaut 1 lorsque seul a ou b vaut 1 et que ET(a, b) donne 1
		 */

		bln <- ((!a && b) || (a && !b));  //!< le '!' permet de transposer le 1 ou 0 dans son état opposé tout en le traitant comme un booléen.
		RETURN bln;
	// FIN SOUS-PROGRAMME

// PROGRAMME: XOR bit-à-bit
	// VARIABLES
		// A, B: entiers
		// binXOR: chaine binaire
		// i: entier (variable compteur)
	// DEBUT
		A <- 1;
		B <- 5;
		binXOR <- '';

		POUR (i=32; i>=0; --i):
			binXOR <- XOR(BIN(A)[i], BIN(B)[i])) . binXOR;
			
		ECRIRE "XOR" . binXOR;
// FIN PROGRAMME

### EOF ###
Voici ce que je pouvais vous dire sur la permutation, n'hésitez absolument pas à poser des questions si certains aspects abordés ne sont pas assez clairs ou manque d'explications, j'y répondrai dans la mesure du possible.
N'hésitez pas non-plus à me corriger si j'ai fait des erreurs ou à apporter des compléments, j'accepte les critiques, remarques et conseils !