Algorithme de permutations

Darkvador

17 février 2013

1- Introduction

Vous avez déjà tous du surement eu besoin ou rèvé d’écrire ou un programme faisant des anagrammes. Pour info un annagramme c’est juste un élément de l’ensemble de toutes les permutations possibles d’une chaine de caractères donnée. Par exemple le mot ”abcd” a pour annagramme, ”abdc”, ”acbd”,”acdb” etc..... Bon je crois que vous avez compris.Et pour le faire vous allez avoir besoin d’un algorithme de permutations. Dans ce tutoriel nous allons decouvrir le mecanisme d’un algorithme de permutations et en écrire un.

2- Les outils

 

Pour bien suivre ce tutoriel vous aurez besoin de :

• Un peu de bon sens..
• Un soupçon d’attention
• Une pincée de Mathématiques.
• Connaitre un langage de programmation, de preference JAVA ou C, C++, etc.
 

3- Problématique

Etant donnée un ensemble d’éléments a₁,a₂,a₃,.......,a_n. Touver toutes les permutations de longueur n pouvant se faire à partir de ces n éléments. Dans le cas d’un mot par exemple, les éléments seraient les lettres qui composent le mot. Et chaque lettre est considéré autant de fois qu’il apparait dans le mot.

Ainsi le mot “abalo” donnerait l’ensemble a,b,a,l,o. Meme si il ya deux fois la lettre ’a’.

4- Les permutations

"En mathématiques, la notion de permutation exprime l’idée de réarrangement d’objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l’ordre de succession de ces n objets. " source wikipedia

Donc une permutation est  un arrangement (car l’ordre des elements compte) de n elements dans n elements. Et la formule qui donne le nombre d’arrangements est :

                             A_n^k =  n!/(n-k)  pour k ≤ n,

En gros on a :

                             A_n^k = n(n-1)(n-2)........(n-k+1)   

Vous comprenez donc que pour k = n, ce nombre equivaut à :

                              n(n-1)(n-2)........3*2*1 = n!

Le n ! se lit factorielle n. Si vous ètes dérouté allez lire ceci, ça vous fera du bien. Plus n est grand, plus n ! est élevé, alors pour trouver toutes les permutations, il faut ecrire un algoritme sérieux. Et nous y venons.

5- Un Peu de pratique

Supposons que je doive trouver les permutations du mot ”abalo”.

Ce mot compte 5 lettres donc je dois avoir en tout N= 5*4*3*2*1= 120 mots. Hmmmm....si vous avez compris cela , alors c’est que vous ètes sur la bonne voie. Mais l’ennui c’est comment les trouver tous sans oublier aucun.

Je vous vois venir. Je fais une permutation circulaire. Je m’explique :

J’ai ”abalo” : jenvoie ”o” à la première place.

J’ai ”oabal” : jenvoie ”l” à la première place

J’ai ”loaba” : jenvoie ”a” à la première place

J’ai ”aloab” : jenvoie ”b” à la première place

J’ai ”baloa” : jenvoie ”a” à la première place

J’ai ”abalo” : Mince je retombe sur le premier

C’est pas grave j’en ai trouvé 5. C’est une blague ! ! ! ! Vous trouvez 5 mots sur 120, et vous ètes contents. Une chose est sure la permutation circulaire va pas le faire..... Mais attendez...Et si pour chaque permutation circulaire je faisais les permutations circulaires des n-1 dernières lettres. On essaie pour voir.

Bon le premier c’est ”abalo”.

je maintiens le ”a” à la première position et je permute le reste.

On a alors :

- ”balo”

- ”obal”

- ”loba”

- ”alob”

Ok on en a trouvé 4.

On recommence avec la meme tactique, sauf que cette fois on garde les deux premieres lettres ”ab”.

- ”alo”

- ”oal”

- ”loa”

Ensuite on garde ”aba” et on a :

- ”lo”

- ”ol”

Enfin on garde ”abal” et on a.

- ”o”

Si vous comptez bien vous voyez que d’abord on est parti de 5 lettres.

Puis pour l’une des permutations de 5 lettres on a trouvé 4 permutations pour les 4 lettres restantes.

- Pour chacune des 4 permutations on a 3 permutations possibles, sans les deux premières lettres.

- Puis deux permutations pour chacune d’elles, sans les trois premières lettres.

- Puis un dernier.

Donc pour ce seul mot de 5 lettres on a trouvé 4*3*2*1 = 24. Et si on fait la meme chose pour tous les 4 autres mots de 5 lettres on a 24*5 = 120 mots

On a trouvé la bonne methode :

Elle consiste juste à fixer une lettre à une position donnée et faire permuter les autres et ainsi de suite.

Mais bon faut quand mème le faire dans le bon ordre sinon, bonjour la performance. Nous allons donc de ce pas ecrire un algorithme qui va exécuter la belle idée que nous venons d’avoir.

6- Methodologie

Nous ne passerons pas par 4 chemins, on sait tous ce qu’il faut faire. Mais concretement pour un ordinateur ça signifie quoi ?Commençons par le commencement .

- On a une chaine de caractère qui represente l’ensemble sur lequel on fera les permutations et qu’il faudra stocker. Pour ça un tableau est très bien vu. Si vous avez une autre préférence, surtout ne vous gener pas.

- Donc T[] sera notre tableau de longueur n.

- Ensuite on fait koi ? On permute d’abord ou on commence par fixer la première lettre. AYAYAYYAYAYAYYA ça commence à se compliquer cette affaire. C’est pour ça que je disais qu’il faut aller en ordre sinon on consomme du temps et de la memoire pour rien.

- On procède donc par niveau. un niveau est represente par le nombre de lettres a permuter. Autrement dit :

- Niveau 1 : n lettres

- Niveau 2 : n-1 lettres

.

. - Niveau n-1 : 2 lettres

Au n-ème niveau il n’ya qu’une seule lettre donc ce n’est pas la peine.

Ce qui nous fait n-1 niveaux de permutations.

Les Etapes à suivre :

- On fait les n premières permutations circulaires

- Pour chaque permutation circulaire : - On fixe la premiere lettre - On fait les n-1 permutations circulaires des lettres restantes - Et on répete le processus jusqu’au dernier niveau.

- Lorsqu’on qu’on atteint le dernier niveau, on affiche le contenu du

tableau.

Autrement dit pour faire une permutation de rang n, on doit faire une permutation de rang n-1. Donc la il y a une recursion. Et le meilleur moyen de dealer avec une récursion c’est utiliser un algorithme récursif.

7- Algorithme 

      - variables
      T[] : tableau de n caractères  ( les tableaux iront de 1 à n)
      i,j,k: iterateur

      Fonction anagramme(T[], entier position)
      Si(n - position) <= 1
          afficher le contenu du tableau
      Sinon
          Pour i allant de 1 à n-1
        faire une permutation circulaire
        faire toutes les permutations circulaires a partir de la case suivante
        FinSi
        Fin

           

8- Implementation en Java

8.1 Methode Principale

La méthode anagramma est la principale ,et cherche les anagrammes de l’ensemble des caractères situés à partir de la position first jusqu’à la position n. C’est une méthode récursive, c’est à dire, une méthode qui contient un appel à elle-mème.

      public void anagramma(char T[],int first) {
        if ((T.length - first) <= 1){
            System.out.println(T);
          }else {
            for (int i = 0; i &lt T.length-first ; i++) {
            round(T, first);
            anagramma(T, first+1);
            }
          }
      }
    

     

Fonctionnement : A l’appel de la méthode on passe en paramètre, le tableau de caractères et la position à partir de laquelle anagramme doit se faire. Si la lettre de depart est aussi celle d’arrivée, la méthode affiche la permutation ainsi obtenue. Sinon elle cherche les anagrammes à partir de la position de départ. Concrètement cela consiste à :

• Fixer la lettre à la position de départ,
• Trouver toutes les permutations circulaires à partir de cette lettre jusqu’à la dernière
• Et pour chaque permutation, chercher les anagrammes à partir de la lettre suivante

8.2 Méthode round

Cette méthode permet de faire une permutation circulaire, a partir de la position i du tableau.

 

    private void round(char T[],int i){
      char temp = T[i];
      for(int j=i;j &lt T.length-1;j++){
          T[j] = T[j+1];

      }
      T[T.length-1]= temp;
    }

Fonctionnement : Cette méthode fait une permutation circulaire delà droite vers gauche en :

•  Sauvegarder le premier element
•  Decaler tous les elements d’un rang vers la gauche, a partir de la position i+1
•  Remettre le premier element à la dernière position

Je sais ce que vous vous dites, tout ce blabla pour un code aussi petit ! ! ! ! ! ! ! Eh oui, tout ça grace à la fonction recursive. Sans elle vous auriez déjà un mal de tète. Si vous ne me croyez pas, essayer pour voir. Mais l’essentiel c’est d’avoir compris la méthodologie qu’il ya derrière.

9- Autres méthodes

Vous devez savoir aussi qu’on aurait pu implementer ce code autrement.

- Une méthode serait de construire un arbre de choix avec les elements de l’ensemble et pour trouver les permutations, il suffirait de parcourir l’arbre de Père e Fils.

- On peut aussi imaginer un ensemble de boucles imbriquées avec astuces, pour réaliser la mème chose. Mais comme je vous l’ai dit, c’est sans moi.

- Il y a aussi toutes les méthodes que je ne connais pas, et dont vous pourriez me parler aussi.

10- Pour aller plus loin

Bien entendu, nous avons parlé d’un algorithme de permutations qui est valable pour n’importe quel type d’éléments. Mais pour le cas spécifiques des anagrammes, il faut bien sur que les permutations correspondent à un mot qui existe pour de vrai. D’où la nécessité de les comparer à une liste de mots d’un dictionnaire par exemple. Le lecteur se fera un plaisir de le faire lui-mème.

11- Code

Le code du tutoriel se trouve à :
         - Code-source
         - Version PDF