céder avec une fonction récursive en python

Question

J'essaie de créer un générateur à des fins de permutation. Je sais qu'il existe d'autres façons de le faire en python. Mais c'est pour autre chose. Mais je ne suis pas capable de donner les valeurs. Pouvez-vous aider?

def perm(s,p=0,ii=0): 
    l=len(s) 
    s=list(s) 
    if(l==1):  
     print ''.join(s) 
    elif((l-p)==2): 
     yield ''.join(s) 
     yield ''.join([''.join(s[:-2]),s[-1],s[-2]]) 
     #print ''.join(s) 
     #print ''.join([''.join(s[:-2]),s[-1],s[-2]]) 
    else: 
     for i in range(p,l): 
      tmp=s[p] 
      s[p]=s[i] 
      s[i]=tmp   
      perm(s,p+1,ii) 

Answer 1

Votre ligne perm(s,p+1,ii) ne fait rien, vraiment: il est comme taper

>>> perm("fred") 
<generator object perm at 0xb72b9cd4> 

Si vous cédez de cet appel, bien que, soit

 for subperm in perm(s, p+1, ii): 
      yield subperm 

alors vous obtenir

>>> list(perm("abc")) 
['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] 
>>> list(perm("abcd")) 
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba'] 

>>> len(_) 
24 
>>> len(set(perm("abcd"))) 
24 

qui a l'air correct. Je n'ai pas testé le code au-delà de ça. Par ailleurs, vous pouvez échanger s[i] et s[p] avec s[i], s[p] = s[p], s[i]; pas besoin d'une variable tmp. PS: à l'heure actuelle, vous ne gérez pas le cas d'un caractère.

Answer 2

Dans un générateur, chaque fois que vous voulez retourner une valeur, vous devez yield. Il est comme vous aviez une fonction factoriel récursive qui ressemblait à ceci:

>>> def fact(n, result=1): 
    if n==0: return result 
    fact(n-1, result*n) 

Et puis vous vous demandez pourquoi il ne retourne rien:

>>> fact(5) 
>>> 

La raison en est que la fonction est appelée récursive, mais la valeur est perdue. Vous voulez faire:

>>> def fact(n, result=1): 
    if n==0: return result 
    return fact(n-1, result*n) 

>>> fact(5) 
120 

De manière analogue, dans la partie récursive de votre algorithme vous:

for i in range(p,l): 
     tmp=s[p] 
     s[p]=s[i] 
     s[i]=tmp   
     perm(s,p+1,ii) 

Cela ne yield rien, cependant, si aucune des valeurs de la perm(s,p+1,ii) l'appel sera retourné (EDIT: en réalité, aucun d'eux ne sera même calculé). Vous aurez envie de parcourir les résultats de l'appel récursif et retourner chacun à son tour:

for i in range(p,l): 
     tmp=s[p] 
     s[p]=s[i] 
     s[i]=tmp   
     for result in perm(s,p+1,ii): 
      yield result