Recherche d'anagrames

L'ensemble des anagrammes peuvent être représentés sous la forme d'un arbre dont les noeuds sont les symboles constituant l'anagramme. La lecture de tous les noeuds d'un chemin de la racine a une feuille constitue la lecture d'un anagramme.

Les noeuds de chaque niveaux correspondent a l'ensemble des symboles de nature différentes et non encore utilisés dans les niveaux superieurs.

Ci-dessous des exemples d'arbres et les paramètres transmis a la fonction récursive permettant la découverte des solutions.

La taille de l'arbre grandit très vite. voici l'arbre des solutions et l'arbre des paramètes pour "jude"

Pour finir, une implémentation en Perl de cette fonction récursive.

# separateur par défaut 
$\="\n";

# search_anagrams affiche tous  les anagrammes du mot fourni en 1er argument
# sur la sortie standard

sub search_anagrams {

    # $src est l'ensemble des caracteres qu'il faut encore inserer dans l'anagramme
    # $dest est un anagramme en cours de construction 

    my ( $src , $dest ) = @_;
    my %still_used;

    # *differentes* de $src, je relance search_anagrams en 
    # déplacant L dans $dest ...

    # pour toutes lettres  de $src
    $src =~ s(.){
        # si non encore utiliseà a ce niveau de rÃecursion ...
        # je deplace cette lettre dans $dest et je lance un nouveau niveau 
        # de recursion
        $still_used{$&}++
            or search_anagrams("$`$'","$dest$&")
    }eg or print "$dest";
    # si s/// renvoie faux, c'est que $dest est complet. Je l'affiche

}

# lance la recherche d'anagramme du mot fourni comme parametre a la ligne de
# commande

search_anagrams(shift);

ou plus simplement

#! /usr/bin/perl -l
sub a{my($s,$d)=@_;my%s;$s=~s(.){$s{$&}++||a("$`$'","$d$&")}eg||print"$d";}a($_)for@ARGV;