Bonjour
Je m'intéresse à la question d'écrire un programme en C pour d'afficher tous les anagrammes d'une chaîne donnée, par exemple, il y a 6 anagrammes de PAPA :
PAPA, APPA, AAPP, PPAA, PAAP, APAP
Mais restons-en aux permutations de n lettres (donc deux à deux distinctes). Je ne m'intéresse pas à un algorithme itératif (l'ordre lexicographique par exemple) mais à un algorithme récursif surtout que cela semble assez adapté à la notion de permutation et de factorielle.
[Au passage, j'ai assez rapidement regardé le fascicule de Knuth et il ne parle pas explicitement me semble-t-il d'algorithme récursif (il en parle pour énumérer les tris topologiques).]
Ainsi, une idée assez naturelle est la suivante:
pour avoir toutes les permutations sur (n+1) lettres il suffit de connaitre toutes les permutations sur les n premières et pour chacune d'elle, interposer la dernière
lettre entre deux lettres (ou une seule aux extrémités) du mot à n lettres. Exemple : les permutations sur 2 lettres sont :
AB
BA
donc pour avoir celles sur A, B et C, je prends la première permutation AB et j'interpose de trois façons la nouvelle lettre C, ce qui donne
CAB
ACB
ABC
et puis on fait de même avec l'autre permutation BA et on obtient ainsi les 6 permutations de A, B, C.
Il y a aussi une autre idée assez naturelle, c'est qu'une fois connues les permutation sur n objets, on consruit les permutations sur (n+1) objets en faisant des échanges (transposition) entre la nouvelle lettre et les anciennes. Illustration :
ABC
BAC
CBA (A<->C)
BCA (A<->C)
ACB (A<->B)
CAB (A<->B)
En théorie c'est bien mais dans la pratique (à implémenter), il me semble que cela nécessite la mémorisation de toutes les permutations sur les n dernières lettres et vu le nombre de permutations, vaut mieux stocker ça dans un fichier qu'en RAM.... Maintenant quelqu'un voit-il une astuce, suivant toujours cette idée d'interposition ou de transposition (parce je sais le faire avec une autre méthode), pour engendrer les permutations à la volée (sans mémoriser ci ce n'est O(n) objets) ?
Partager