Générer les anagrammes d'un mot

**Flo963** · 08/08/2013, 15h49

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** · 08/08/2013, 16h38

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** · 08/08/2013, 18h08

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** · 08/08/2013, 20h49

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** · 09/08/2013, 17h13

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** · 09/08/2013, 17h50

> 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 ?

**wiztricks** · 09/08/2013, 19h53

Salut,
Si on dit que:
* permuter ('yz') donne 'yz', 'zy', alors
* permuter ('xyz') s'obtient en insérant 'x' (le premier élément) a toutes les positions des chaînes produites par permuter('yz'). Ce qui donne:

pour 'yz': 'xyz', 'yxz', 'yzx'
pour 'zy': 'xzy', 'zxy', 'zyx'

Ce qui se traduit assez simplement en "Python":

Code :

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

1
2
3
4
5
 
     liste=[]     
     for p in permuter(items[1:]):
         for i in range(len(items)):
             liste.append((p[:i]+items[0:1]+p[i:])

En ajoutant les conditions aux limites, on obtient:

Code :

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

1
2
3
4
5
6
7
8
def permuter(items):
    if len(items) <= 1:
        return [items]
    liste=[]
    for p in permuter(items[1:]):
        for i in range(len(items)):
            liste.append(p[:i]+items[0:1]+p[i:])
    return liste

Tous les algos. proposes font la même chose.
La différence étant l'inversion caractères/permutations que je trouve un peu décalée, compliquée... Essayez d’écrire le truc en français, pour voir a quoi ressemble le "haut niveau". On peut lire les commentaires et y croire, y retrouver ses petits... Mais bon ça fonctionne.
- W

**mont29** · 09/08/2013, 21h24

Effectivement, nos trois codes font la même chose, de façon plus ou moins élégante (je n’avais pas vraiment eu le temps de “lécher” le mien

). J’aime beaucoup celui de wiztricks (au passage, remarquons le subtile p[:i]+items[0:1]+p[i:] au lieu de p[:i]+items[0]+p[i:], qui permet d’utiliser ce code avec n’importe quel type “séquence”*!

).

@Flo963*:
* mot = chaine, c’était pour éviter de modifier la chaine originale, mais ça ne sert en fait à rien puisqu’on n’en a plus besoin par la suite…
* list(liste), c’est un grand classique des itérations sur une liste quand on modifie celle-ci dans l’itération. À quelques exceptions prêt (et à condition de savoir vraiment ce que l’on fait), il faut alors itérer sur une copie de la liste, sinon on risque de se retrouver à traiter des éléments non voulus, et à en ignorer d’autres…
* Le [e for e in foo][1:] permet de ne pas utiliser le premier élément généré par la list comprehension, tout simplement (qui se trouve ici le même que le mot d’origine).

**mont29** · 09/08/2013, 22h55

Comme je suis particulièrement vicieux, maintenant qu’on a un algo récursif simple à comprendre, je l’ai “dé-récursivé”… Bon appétit*!

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
import math
 
def permuter(items):
    ln = len(items)
    if ln > 10:
        raise ValueError("We can't compute all the permutations of sequence lengther than 10 items!")
    if ln <= 1:
        return [items]
    num = math.factorial(ln)
    liste = [None] * num
    liste[0] = items
    fact = 1
    offset = num
    while (fact < ln):
        items = liste[:num:offset]
        fact += 1
        offset = num // math.factorial(fact)
        idx = 0
        for it in items:
            idx += offset
            rad, c, end = it[:-fact], it[-fact], it[-fact + 1:]
            for i in range(1, fact):
                liste[idx] = rad + end[:i] + c + end[i:]
                idx += offset
    return liste

[EDIT] On peut gagner énormément en mémoire en utilisant itertools.islice, au lieu de copier jusqu’à la moitié de la liste…

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
import math, itertools
 
def permuter(items):
    ln = len(items)
    if ln > 10:
        raise ValueError("We can't compute all the permutations of sequence lengther than 10 items!")
    if ln <= 1:
        return [items]
    num = math.factorial(ln)
    liste = [None] * num
    liste[0] = items
    fact = 1
    offset = num
    while (fact < ln):
        items = itertools.islice(liste, 0, num, offset)
        fact += 1
        offset = num // math.factorial(fact)
        idx = 0
        for it in items:
            idx += offset
            rad, c, end = it[:-fact], it[-fact], it[-fact + 1:]
            for i in range(1, fact):
                liste[idx] = rad + end[:i] + c + end[i:]
                idx += offset
    return liste

**Flo963** · 10/08/2013, 13h57

> mont29, merci pour tes explications. Je crois que je vais m'arrêter avant la dé-récursivité, avant que ma tête n'explose

> wiztricks, effectivement c'est le moyen le plus simple de présenter l'algorithme.
La récursivité n'est pas encore très claire pour moi. pas assez en tout cas pour pouvoir la réutiliser. Mais ça me donne un bon aperçu en tout cas.

**wiztricks** · 10/08/2013, 16h37

Salut,

Envoyé par Flo963

La récursivité n'est pas encore très claire pour moi. pas assez en tout cas pour pouvoir la réutiliser. Mais ça me donne un bon aperçu en tout cas.

La récursivité est un sujet assez difficile. Elle permet de coder simplement des algorithmes passablement compliques a coder "sinon".
Regardez le code de-recurse (aie!) qu'a gentiment pondu mont29: heureusement qu'on sait ce que ça fait!
Imaginez devoir le sortir en lisant le code: galère!

- W

**dividee** · 10/08/2013, 17h44

Envoyé par mont29

Comme je suis particulièrement vicieux, maintenant qu’on a un algo récursif simple à comprendre, je l’ai “dé-récursivé”… Bon appétit*!

A vicieux, vicieux et demi

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 permuts(seq):
    results = []
    seq = list(seq)
    results.append(tuple(seq))
    i = 0
    while 1:
        i += 1
        n,d,r = i, 1, 0         # numerator, divisor, rest
        while r == 0:
            d += 1
            n, r = divmod(n, d)
        if d > len(seq): break
        seq[-d], seq[-r] = seq[-r], seq[-d] # swap
        seq[-d+1:] = seq[-1:-d:-1]          # reverse the end
        results.append(tuple(seq))
    return results

[edit]
Quelques explications:

Si on observe la séquence des permutations dans l'ordre lexicographique, on peut remarquer qu'on peut à chaque fois passer d'une permutation à la suivante en faisant un échange suivi d'une inversion de la fin de la séquence.

Par exemple:
0 3 5 4 2 1
échanger 3 et 4 --> 0 4 5 3 2 1
inverser ce qui suit le 4 --> 0 4 1 2 3 5
ce qui est bien la permutation qui suit 0 3 5 4 2 1.

Ensuite il "suffit" de déterminer quelle paire échanger à chaque étape.
* Une fois sur deux, la permutation concerne les deux derniers éléments de la séquence (positions -2 et -1 avec l'indexage python)
* En éliminant les cas précédents, deux fois sur trois, elle concerne l'élément en position -3, le second élément alternant entre les deux dernières positions
* Parmi les cas restants, 3 sur 4 concernent l'élément en position -4, le second élément alternant entre les trois dernières positions
et ainsi de suite.

En formalisant cela, j'arrive au code ci-dessus.

**mont29** · 10/08/2013, 19h05

Que voilà un bel algo*!

Mais si je puis me permettre, je suis à peu près persuadé qu’il est préférable de calculer une seule fois la factorielle de n plutôt que de tester fact(n) fois une condition…

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
import math   # Ou définition de notre propore fonction factorial, ce n’est pas bien compliqué
 
def permuts(seq):
    totlen = math.factorial(len(seq))
    results = [None] * totlen
    seq = list(seq)
    results[0] = tuple(seq)
    for i in range(1, totlen):
        n, d, r = i, 1, 0         # numerator, divisor, rest
        while r == 0:
            d += 1
            n, r = divmod(n, d)
        seq[-d], seq[-r] = seq[-r], seq[-d] # swap
        seq[-d + 1:] = seq[-1:-d:-1]        # reverse the end
        results[i] = tuple(seq)
    return results

Ceci dit, cet algo n’a pas l’air très performant (_a est la fonction de wiztricks, _b la mienne, _c celle de dividee et _d ma version optimisée de _c)*:

Code :

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

1
2
3
4
5
6
7
8
9
>>> check("123456789", 10)
permuts_a('123456789') 10 times:
	4.787833017995581
permuts_b('123456789') 10 times:
	4.363410446036141
permuts_c('123456789') 10 times:
	7.646154345013201
permuts_d('123456789') 10 times:
	6.989068745984696

Code :

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

1
2
3
4
5
6
7
8
9
>>> check("12345", 10000)
permuts_a('12345') 10000 times:
	1.5854012399795465
permuts_b('12345') 10000 times:
	1.678863559034653
permuts_c('12345') 10000 times:
	3.272084306983743
permuts_d('12345') 10000 times:
	2.4538890609983355

D’où l’on peut conclure que pour un algo de ce type, où l’occupation mémoire et le nombre d’itérations exploseront bien avant d’avoir atteint une profondeur de récursion problématique, pas la peine de se fatiguer à dérécursiver les choses…

Pour info, voici le code complet*:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import math  # Ou définition de notre propore fonction factorial, ce n’est pas bien compliqué
import itertools
 
def permuts_a(items):
    items = tuple(items)
    ln = len(items)
    if ln <= 1:
        return [items]
    liste=[]
    for p in permuts_a(items[1:]):
        for i in range(ln):
            liste.append(tuple(p[:i] + items[0:1] + p[i:]))
    return liste
 
def permuts_b(items):
    items = tuple(items)
    ln = len(items)
    if ln > 10:
        raise ValueError("We can't compute all the permutations of sequence lengther than 10 items!")
    if ln <= 1:
        return [items]
    num = math.factorial(ln)
    liste = [None] * num
    liste[0] = items
    fact = 1
    offset = num
    while (fact < ln):
        items = itertools.islice(liste, 0, num, offset)
        fact += 1
        offset = num // math.factorial(fact)
        idx = 0
        for it in items:
            idx += offset
            rad, c, end = it[:-fact], it[-fact:-fact + 1], it[-fact + 1:]
            for i in range(1, fact):
                liste[idx] = tuple(rad + end[:i] + c + end[i:])
                idx += offset
    return liste
 
def permuts_c(seq):
    results = []
    seq = list(seq)
    results.append(tuple(seq))
    i = 0
    while 1:
        i += 1
        n,d,r = i, 1, 0         # numerator, divisor, rest
        while r == 0:
            d += 1
            n, r = divmod(n, d)
        if d > len(seq): break
        seq[-d], seq[-r] = seq[-r], seq[-d] # swap
        seq[-d+1:] = seq[-1:-d:-1]          # reverse the end
        results.append(tuple(seq))
    return results
 
def permuts_d(seq):
    totlen = math.factorial(len(seq))
    results = [None] * totlen
    seq = list(seq)
    results[0] = tuple(seq)
    for i in range(1, totlen):
        n, d, r = i, 1, 0         # numerator, divisor, rest
        while r == 0:
            d += 1
            n, r = divmod(n, d)
        seq[-d], seq[-r] = seq[-r], seq[-d] # swap
        seq[-d + 1:] = seq[-1:-d:-1]        # reverse the end
        results[i] = tuple(seq)
    return results
 
def check(items, num=1000):
    import timeit
    print("permuts_a({}) {} times:\n\t{}".format(repr(items), num,
          timeit.timeit("permuts_a({})".format(repr(items)), setup="from __main__ import permuts_a", number=num)))
    print("permuts_b({}) {} times:\n\t{}".format(repr(items), num,
          timeit.timeit("permuts_b({})".format(repr(items)), setup="from __main__ import permuts_b", number=num)))
    print("permuts_c({}) {} times:\n\t{}".format(repr(items), num,
          timeit.timeit("permuts_c({})".format(repr(items)), setup="from __main__ import permuts_c", number=num)))
    print("permuts_d({}) {} times:\n\t{}".format(repr(items), num,
          timeit.timeit("permuts_d({})".format(repr(items)), setup="from __main__ import permuts_d", number=num)))

**wiztricks** · 11/08/2013, 16h56

Salut,

Mettre une fonction récursive a plat c'est remplacer l'overhead des save/restore des appels de fonctions par la gestion de structures ad hoc. On y gagnera si on compense le "plus" d'instructions par une réduction de la bande passante utilisée cote mémoire.
Note: Avec Python tout étant objet et la machine virtuelle "a pile", les "gains" sont plus compliques a évaluer.

La complexité de l'algo étant ~fact(n), ou n est longueur de "items".
On peut se dire "chouette", factorielle(n) même multiplie par un epsilon devrait être intéressant.

D’où l’on peut conclure que pour un algo de ce type, où l’occupation mémoire et le nombre d’itérations exploseront bien avant d’avoir atteint une profondeur de récursion problématique, pas la peine de se fatiguer à dérécursiver les choses…

Relisez mon code: permuter n'est appelé que n fois alors que le gros du boulot ( factorielle n-1) est dans la boucle for i in range(len(items)).
- W

**stalacta** · 13/08/2013, 11h35

Voici ma suggestion :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
def anagrammes(chaine) :
	liste=[chaine]
	for i in range(len(chaine)):
		for ii in range(i+1,len(chaine)):
			mot=''
			for iii in range(len(chaine)):
				if iii==i : mot+=chaine[ii]
				elif iii==ii : mot+=chaine[i]
				else : mot+=chaine[iii]
			liste.append(mot) # si tu veux avoir toutes les possibilités avec doublons
                        # sinon if mot not in liste : liste.append(mot)
	return liste

edit : je me suis rendu compte qu'il n'y a pas tous les mots

**Flo963** · 16/08/2013, 18h41

Bonjour,

@wiztricks je m'intéresse au code que vous avez posté. Ce que j'en ai compris, c'est que l'appel récursif s'applique au (nombre de lettre -1) jusqu'à arriver au cas où il n'y a plus qu'une seule lettre. Cependant ce que je comprends mal, c'est que si la variable 'p' correspond à chaque fois à un nombre de lettre plus petit, comment se fait-il que le code renvoie bien une liste de mots composés du même nombre de lettres que le mot d'origine ?
Je ne sais pas si je suis clair mais pourriez-vous détailler un peu plus le fonctionnement du code (sans vouloir abuser

) ?

**Sve@r** · 17/08/2013, 13h18

Envoyé par Flo963

Bonjour,

@wiztricks je m'intéresse au code que vous avez posté. Ce que j'en ai compris, c'est que l'appel récursif s'applique au (nombre de lettre -1) jusqu'à arriver au cas où il n'y a plus qu'une seule lettre. Cependant ce que je comprends mal, c'est que si la variable 'p' correspond à chaque fois à un nombre de lettre plus petit, comment se fait-il que le code renvoie bien une liste de mots composés du même nombre de lettres que le mot d'origine ?
Je ne sais pas si je suis clair mais pourriez-vous détailler un peu plus le fonctionnement du code (sans vouloir abuser

) ?

Bonjour
p ne correspond pas au nombres de lettres mais aux mots renvoyés par l'appel inférieur ; mots situés dans une liste de mots construite lors de l'appel inférieur.

Prenons l'exemple de "abc". La fonction commence
1) elle reçoit "abc" et commence une boucle sur for p in permuter("bc").
2) elle reçoit "bc" et commence une boucle sur for p in permuter("c").
3) len("c") étant <= 1, elle renvoie ["c"]

2) retour au niveau supérieur qui reçoit le tableau ["c"]. p commence donc son itération sur chaque élément du tableau donc sur "c". Là, seconde boucle for i in [0, 1]. Cela créera une liste contenant p[:0](="") + "b" + p[0:](="c") soit "bc" puis p[:1](="c") + "b" + p[1:](="") soit "cb". La fonction renvoie donc ["bc", "cb"]

1) retour au niveau supérieur qui reçoit le tableau ["bc", "cb"]. p commence son itération sur "bc". Là, seconde boucle for i in [0, 1, 2] cette fois. Cela créera une liste contenant p[:0](="") + "a" + p[0:](="bc") soit "abc" puis p[:1]("=b") + "a" + p[1:](="c") soit "bac" puis p[:2](="bc") + "a" + p[2:](="") soit "bca"

1) p continue sur le second élément du tableau et itère donc sur "cb". De nouveau seconde boucle for i in [0, 1, 2]. Cela continuera la liste contenant contenant p[:0](="") + "a" + p[0:](="cb") soit "acb" puis p[:1]("=c") + "a" + p[1:](="b") soit "cab" puis p[:2](="cb") + "a" + p[2:](="") soit "cba"

1) la fonction renvoie donc ["abc", "bac", "bca", "acb", "cab", "cba"]

Et si ce "1" était lui-même issu d'un appel supérieur (par exemple permuter("xabc")) alors même système toutefois de plus en plus complexe puisque p itèrerait sur 6 éléments tandis que la boucle i serait sur [0, 1, 2, 3] cette fois (on retrouve d'ailleurs le calcul factoriel qui dit que permuter n lettres donne n! solutions).

@wiztricks: super algo

**wiztricks** · 17/08/2013, 14h30

Envoyé par Flo963

Ce que j'en ai compris, c'est que l'appel récursif s'applique au (nombre de lettre -1) jusqu'à arriver au cas où il n'y a plus qu'une seule lettre. Cependant ce que je comprends mal, c'est que si la variable 'p' correspond à chaque fois à un nombre de lettre plus petit, comment se fait-il que le code renvoie bien une liste de mots composés du même nombre de lettres que le mot d'origine ?

Soit vous faites des petits dessins pour simuler les appels: a chaque appel, il y a un contexte et un reste a faire: au retour, sont construits les mots de longueur +1.
Soit vous procédez par induction, ce qui vous renvoie sur un truc semblable a ce que j'avais poste initialement.

Dans tous les cas, c'est gymnastique de l'esprit que vous devrez acquérir avant d’espérer avoir compris. Vous raconter les choses d'une façon plus ou moins attrayante pourra vous motiver a gratter cela par vous même. Mais le gros du boulot reste a faire de votre cote.

- W

**Flo963** · 18/08/2013, 15h57

Merci pour vos réponses.
Sve@r, merci pour cette explication détaillée, je vois mieux comment fonctionne le code maintenant.
Ce n'est pas très important mais si je ne me trompe pas, pour le cas de base, inutile d'écrire 'return [items]', 'return items' suffit.

**Sve@r** · 18/08/2013, 16h47

Envoyé par Flo963

Ce n'est pas très important mais si je ne me trompe pas, pour le cas de base, inutile d'écrire 'return [items]', 'return items' suffit.

Hé non, ceci est au contraire très important. Il est absolument nécessaire que le dernier appel renvoie un tableau car l'appel supérieur a instancié une boucle sur chaque élément du tableau renvoyé par l'appel inférieur.

Cependant on peut remplacer le tableau par un yield (un générateur) car for x in generateur() se comporte de la même façon que for x in [tableau] tout en consommant moins de mémoire.

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
def permuter(items):
    if len(items) <= 1:
        yield items
        return
    # if
    for p in permuter(items[1:]):
        for i in range(len(items)):
            yield p[:i]+items[0:1]+p[i:]
    # for
# permuter()
 
for mot in permuter("abc"): print mot

Générer les anagrammes d'un mot

Python

Discussions similaires

Partager

Partager