Discussion :

[Kazvert]

Bonjour,

Je n'arrive pas à présenter le résultat sous la bonne forme. En donnant le string 'abc', j'ai le résultat suivant : ["a['bc', 'cb']", "b['ac', 'ca']", "c['ab', 'ba']"].

Je ne vois pas du tout comment distribuer le a dans bc et cb pour avoir abc et acb. Quand on "remonte" la recursion, on a bien bc et cb mais la "remontée" suivante avec a se passe mal.

Pour la récursion j'utilise :
Arret Rec : len(my_string)==1
Rec : per(a,b,c) = a + per(b,c) , b + per(a,c) , c + per(a,b)
per(b,c) donne b+per(c) et c+per(b).
per(c) donne c donc bc donc abc.

Code :

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

1
2
3
4
5
6
7
8
9
10
def permut(my_string):
    result=[]
    if len(my_string)==1:
        return my_string
    else:
        for i,elt in enumerate(my_string):
            result.append(elt+str(permut(my_string[:i]+my_string[i+1:])))            
    return result       
 
print(permut('abc'))

Merci

[Sve@r]

Je n'arrive pas à présenter le résultat sous la bonne forme. En donnant le string 'abc', j'ai le résultat suivant : ["a['bc', 'cb']", "b['ac', 'ca']", "c['ab', 'ba']"].

Bonjour

C'est normal, dans un cas ta fonction retourne une string (la fin de récursivité) et dans l'autre cas elle retourne un tableau. Donc en fin de récursivité tu accoles une string au caractère traité dans la boucle mais dans les appels supérieurs tu accoles un tableau à ce caractère.
Pour qu'une fonction (même récursive) puisse être convenablement traitée, il faut qu'elle renvoie toujours la même chose. Ou alors tu analyses le type reçu mais là ça devient usine à gaz...

C'est faisable avec des tableaux mais si tu connais yield ce sera plus facile.

[Kazvert]

D'accord, je vois le problème. Filtrer les résultats suivants que l'on ressort string ou tableau ne m'apparait pas non plus la meilleurs solution

Pour le moment, je ne maitrise pas vraiment yield et cela ne marche pas mais cela me donne une bonne piste

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
def permut(my_string):
    result=[]
    if len(my_string)==1:
        return my_string
    else:
        for i,elt in enumerate(my_string):
            inter_result.append(yield(permut(my_string[:i]+my_string[i+1:]))  )
            for elt2 in inter_result:
                result.append(elt+elt2)
            inter_result=[] 
    return result       
 
A=(permut('abc'))
 
# A => <generator object permut at 0x000000B5F61AD410> et le parcourir ne donne rien

[Sve@r]

D'accord, je vois le problème. Filtrer les résultats suivants que l'on ressort string ou tableau ne m'apparait pas non plus la meilleurs solution

Exact.

Pour le moment, je ne maitrise pas vraiment yield et cela ne marche pas mais cela me donne une bonne piste

Si tu ne le maitrises pas, ne pars pas dessus.

Je vais te donner la solution parce que déjà je t'ai envoyé bêtement sur une fausse piste et j'en suis désolé. En fait, t'as le droit de renvoyer une string en fin de récursivité parce qu'à ce moment, une string de 1 car équivaut à un tableau de 1 élément (ils sont tous deux itérables de la même façon).
En fait, ton premier code était presque bon. Simplement il fallait juste te souvenir que le retour du niveau précédent est lui-même un tableau donc il faut aussi itérer dessus (chose que tu ne faisais pas)

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
12
def permut(my_string):
	if len(my_string) == 1: return my_string
 
	ret = []
	for i in xrange(len(my_string)):
		for x in permut(my_string[0:i] + my_string[i+1:]):
			ret.append(my_string[i] + x)
	# for
	return ret
# permut()
 
print(permut("abc"))

Une fois que ça fonctionne avec un tableau, le transformer en générateur devient trivial. Suffit de replacer toute modification du tableau de retour par un yield. Exemple le tableau est modifié par le ret.append(my_string[i] + x) alors on le remplace par un yield my_string[i] + x. Bien entendu on ne retourne plus le tableau puisque le yield renvoie un générateur qui sera itérable par l'appelant exactement comme s'il recevait un tableau.
Et on n'oublie pas non plus le return de fin de récursivité.
Ce qui donne alors

Code python :

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

1
2
3
4
5
6
7
8
9
10
def permut(my_string):
	if len(my_string) == 1: yield my_string
 
	for i in xrange(len(my_string)):
		for x in permut(my_string[0:i] + my_string[i+1:]):
			yield my_string[i] + x
	# for
# permut()
 
print(tuple(permut("abcd")))

[Kazvert]

Merci pour ta réponse.

La double boucle est pas mal pour résoudre le problème.

" le retour du niveau précédent est lui-même un tableau donc il faut aussi itérer dessus". Effectivement j'avais bien ['bc', 'cb'] par exemple et la boucle permet de "distribuer le string 'a' "

Pour le yield, je vois un peu prés, mais je vais faire quelques exercices / cas plus simples avant de revenir à cette option.

[Sve@r]

Pour le yield, je vois un peu prés, mais je vais faire quelques exercices / cas plus simples avant de revenir à cette option.

En fait, un yield renvoie un truc qui, du côté de l'appelant, sera itérable. C'est donc presque comme un tableau (car un tableau est à la base itérable).

Exemple

Code python :

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

1
2
3
4
def fct():
	return [1, 2, 3, 4, 5]
 
toto=fct()

Ici, toto c'est un tableau. On peut donc accéder à un élément par son index, à un sous-groupe par un slice, modifier/rajouter des éléments, et aussi itérer dessus => for x in toto: print x.

Si ton seul besoin est d'itérer dessus (ce qui arrive, disons le, dans 90% des cas), alors t'as plus besoin d'un tableau mais seulement d'un truc sur lequel on peut itérer => un générateur. On remplace alors, dans la fonction, chaque élément du tableau par un yield.

Code python :

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

1
2
3
4
5
6
7
8
def fct():
	yield 1
	yield 2
	yield 3
	yield 4
	yield 5
 
toto=fct()

Dans cette seconde version, déjà gros gain de mémoire tout en gardant l'itération sur toto possible => for x in toto: print x. Et si (par le plus grand des hasards) il arrivait que tu aies une fois besoin de "toto" en tant que tableau, cela reste possible => toto=list(fct()).