Discussion :

[Flo963]

Bonjour,

J'essaye de faire cet exercice et je suis bloqué (je suis nouveau en programmation). J'ai trouvé une méthode pour trouver les anagrammes qui marche sur le papier et que j'ai écrite clairement. Ca donne ça :

Pour le mot:
Renvoyer le mot
et en créer un autre en permutant les deux premières lettres
Puis pour chacun des deux mots obtenus:
en créer un autre en permutant la troisième et la deuxième lettre
et un autre en permutant la deuxième lettre et la première lettre
(à partir du mot obtenu)
Puis pour chacun des quatre mots obtenus:
en créer un autre en permutant la quatrième lettre à la troisième lettre
et un autre en permutant la troisième lettre et la deuxième
et un autre en permutant la deuxième et la première lettre
Puis pour chacun des seize mots obtenus:
en créer un autre en permuttant la cinquième et la quatrième lettre,
et ainsi de suite...

A partir de là j'ai fait des bouts de code pour permutter les lettres à l'intérieur du mot :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#Le code qui permutte les deux premières lettres du mot:
 
set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(0,1))
 
#Le code qui permutte la troisième et la deuxième lettre du mot:
 
set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(1,2))
 
#Le code qui permutte la quatrième et la troisième lettre du mot:
 
set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(2,3)

Voilà, maintenant l'idée pour pouvoir écrire la fonction, c'est que chacune de ces lignes de code puisse s'appliquer aux résultats de la précédentes. Et là je sèche...Si quelqu'un peut m'indiquer comment faire...

PS: je sais que mon code ne sera de toute façon pas optimisé, et que tout ça doit pouvoir être factorisé mais j'en suis clairement pas encore là.

[Flo963]

Je précise ma question, en suivant la méthode trouvée sur papier ça donne ce code là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def anagrammes(chaine):
 
    liste=[]
 
    chaine1=chaine #1ere etape de la methode
    liste.append(chaine1)
    chaine2=''
    for i in range(0,1):
        chaine2+=chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    liste.append(chaine2)
 
    chaine3='' #2eme etape pour le premier mot cree
    for i in range(1,2):
        chaine3+=chaine1[:i]+chaine1[i+1]+chaine1[i]+chaine1[i+2:]
    liste.append(chaine3)
    chaine4=''
    for i in range(0,1):
        chaine4+=chaine3[:i]+chaine3[i+1]+chaine3[i]+chaine3[i+2:]
    liste.append(chaine4)
 
    chaine5='' #2eme etape pour le deuxieme mot cree
    for i in range(1,2):
        chaine5+=chaine2[:i]+chaine2[i+1]+chaine2[i]+chaine2[i+2:]
    liste.append(chaine5)
    chaine6=''
    for i in range(0,1):
        chaine6+=chaine5[:i]+chaine5[i+1]+chaine5[i]+chaine5[i+2:]
    liste.append(chaine6)
 
    # et ainsi de suite...
 
    return liste

qui fonctionne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
>>> anagrammes('iles')
['iles', 'lies', 'iels', 'eils', 'leis', 'elis']

mais évidemment c'est carrément lourd, mais pour faire une boucle là-dessus je bloque. Si quelqu'un a une suggestion...

[mont29]

En fait, les anagrammes d’un mot se rapprochent de ce qu’on appelle en combinatoire les permutations de ses lettres… Il y a un module dans Python qui fait ça très bien, itertools*:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
import itertools as it
word = "iles"
set("".join(e) for e in it.permutations(word, len(word)))

Maintenant que tu est bien dégoûté , revenons à ton code.

De façon général, le type d’algo que tu décris se prête très bien à la récursion*: tu fais une fonction qui effectue l’opération “noyau” sur le paramètre passé, puis qui s’appelle elle-même sur les résultats de cette opération. Avec ton code, cela donnerait par exemple*:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def anagrammes(chaine, i):
    liste = [chaine]
    # Cette partie génère différentes permutations de chaine en descendant la lettre i jusqu’à l’amener en première position
    mot = chaine
    for ii  in range(i, -1, -1):  # donnera les nombres i, i-1, i-2, ..., 0
        mot = mot[:ii] + mot[ii + 1] + mot[ii] + mot[ii + 2:]
        liste.append(mot)
 
    # et on applique le même processus à tous les mots obtenus, pour la lettre i + 1.
    i += 1
    if i < len(chaine) - 1:
        for mot in list(liste):
            liste +=  anagrammes(mot, i)
 
    return liste
 
anagrammes("iles", 0)

À noter que ce code est loin d’être optimal, et génère des doublons (que l’on peut virer avec l’utilisation d’un set(), par exemple ).

Un moyen plus efficace d’utiliser la récursion est d’appliquer cet algo*: Inverser la première lettre avec toutes les autres, puis pour chaque mot obtenu, appliquer à nouveau cette opération , mais en partant de la lettre suivante (donc sur des mots de longueur n - 1)*:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def anagrammes(chaine):
    liste = [chaine]
    # On permute la première lettre avec chacune des autres lettres.
    for i in range(1, len(chaine)):
        liste.append(chaine[i] + chaine[1:i] + chaine[0] + chaine[i + 1:])
 
    # et on applique le meme processus a tous les mots obtenus, en partant de la lettre suivante comme base.
    if len(chaine) > 2:
        for mot in list(liste):
            liste += [mot[0] + term for term in anagrammes(mot[1:])][1:]  # Le premier element de la liste retournee est le meme que celui de depart!
 
    return liste
 
anagrammes("iles")

[dividee]

Le principe, pour concevoir un algorithme récursif, c'est de trouver un moyen de se ramener à une instance "plus simple" du même problème. "Plus simple" veut ici dire "plus petite". A force de "simplifier", on arrivera a un cas de base trivial à résoudre.

C'est le même principe que l'induction en mathématiques: pour prouver une propriété pour tout entier naturel N, il faut la prouver pour 0 (cas de base), et la prouver pour N (>0) en faisant l'hypothèse qu'elle est valide pour N-1 (cas inductif).

Ici, ce qui est tout naturel comme mesure de la "simplicité", c'est la longueur de la chaîne de caractères.
Comment peut-on générer les permutations de N caractères si on sait déjà générer les permutations de N-1 caractères ? Ca n'est pas bien compliqué: on choisit le premier caractère (cela peut être n'importe lequel, on va donc faire une boucle), et on génère toutes les permutations possibles pour les N-1 caractères restants.

Le cas de base c'est une chaine de longueur 1 (ou 0), pour lequel il n'y a qu'une seule permutation possible, on retournera donc une liste de permutations qui ne contient qu'un seul élément: la chaîne elle-même.

En code cela donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def permut(chaine):
    if len(chaine) <= 1:
        # cas de base
        return [chaine]
    # cas récursif
    liste = []
    # pour chaque caractère de la chaîne
    for i in range(len(chaine)):
        # on l'extrait et on calcule le reste
        c = chaine[i]
        reste = chaine[:i] + chaine[i+1:]
        # pour chaque permutation du reste
        for p in permut(reste):
            # on génère une permutation de la chaine de départ en lui ajoutant le caractère extrait
            liste.append(c+p)
    return liste

Pour le fun, on peut écrire ça en une seule ligne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
def permut(s):
    return [s[i] + p for i in range(len(s)) for p in permut(s[:i] + s[i+1:])] if len(s) > 1 else [s]

Cet algo, c'est un peu un cas d'école pour montrer la puissance de la récursivité.

[Flo963]

Bonjour,

Merci pour vos réponses,

> mont29, le premier code que tu proposes est tout à fait ce que je cherchais même si je crois que je n'aurai jamais trouvé ça tout seul .

> dividee, je n'ai pas réussi à comprendre comment fonctionne ton code dans le détail (je crois que c'est encore le niveau au-dessus). J'essaierai sans doute d'y revenir.

merci en tout cas!

[Flo963]

> mont29
J'ai plusieurs questions:
A quoi sert le 'mot=chaine' à la ligne 4?
Peux-tu me dire pourquoi à la ligne 12 de ton premier code ne peut-on pas boucler directement sur la liste (il faut faire list(liste))?

Dans ton deuxième code, qu'est-ce que le [:1] à la suite de la compréhension de liste à la ligne 10 ?