Présentation de l'algorithme

L'algorithme d'énumération de Tserouf, développé par le Kabbaliste Abraham Aboulafia au 13e siècle, est un procédé systématique pour énumérer toutes les permutations possibles d'un mot de n lettres. Ce procédé est basé sur deux règles : la règle du miroir, qui stipule que la séquence doit se terminer par l'inverse de son début, et la règle de maintien de la tête, qui consiste à conserver la première lettre le plus longtemps possible avant de la laisser aller.

Fonctionnement de l'algorithme

Pour un mot de trois lettres, Aboulafia donne explicitement les six permutations possibles, qui sont regroupées en trois ensembles en fonction de leur première lettre. Les deux règles mentionnées ci-dessus sont presque suffisantes pour déterminer l'ordre des permutations. La règle du miroir fixe le début et la fin de la séquence, tandis que la règle de maintien de la tête détermine l'ordre des lettres dans chaque ensemble.

Étendre l'algorithme à n+1 lettres

Pour passer d'un mot de n lettres à un mot de n+1 lettres, Aboulafia propose une règle supplémentaire : faire tourner le mot d'une lettre. Cela signifie que la première lettre est déplacée à la fin du mot, ce qui donne un nouveau mot. En appliquant les mêmes règles aux lettres restantes, on obtient un nouvel ensemble de permutations. Ce procédé est récursif, ce qui signifie qu'il peut être appliqué à nouveau et à nouveau pour générer toutes les permutations possibles.

Implications et limites

L'algorithme d'Aboulafia est remarquable car il est basé sur une opération simple et récursive qui peut être appliquée à des mots de n'importe quelle longueur. Cette approche est très efficace et permet de générer toutes les permutations possibles sans répétition. Il est intéressant de noter que cet algorithme a été redécouvert au 17e siècle par les change-ringers anglais, et qu'il a des liens avec des algorithmes modernes de traitement des permutations.

abcd -> bcda -> cdab -> dabc

Ce code montre comment l'algorithme d'Aboulafia peut être appliqué pour générer les permutations d'un mot de quatre lettres. La première lettre est déplacée à la fin du mot, puis les mêmes règles sont appliquées aux lettres restantes pour générer un nouvel ensemble de permutations.