Si prega di spiegare questo algoritmo per ottenere tutte le permutazioni di una stringa

Question

Il codice seguente genera tutte le permutazioni di una stringa:

def permutations(word): 
    if len(word)<=1: 
     return [word] 

    #get all permutations of length N-1 
    perms=permutations(word[1:]) 
    char=word[0] 
    result=[] 
    #iterate over all permutations of length N-1 
    for perm in perms: 
     #insert the character into every possible location 
     for i in range(len(perm)+1): 
      result.append(perm[:i] + char + perm[i:]) 
    return result 

puoi spiegare come funziona? Non capisco la ricorsione.

Answer 1

L'algoritmo è:

• Rimuovere la prima lettera
• Trova tutte le permutazioni delle lettere rimanenti (passo ricorsivo)
• reinserire la lettera che è stato rimosso in ogni posizione possibile.

Il caso base per la ricorsione è una singola lettera. C'è solo un modo per permutare una singola lettera.

Ha lavorato esempio

Immaginate la parola inizio è bar.

• Rimuovere prima il b.
• Trova le permutazioni di ar. Questo dà ar e ra.
• Per ciascuna di queste parole, mettere il b in ogni località:
  • ar ->bar, abr, arb
  • ra ->bra, rba, rab

Answer 2

I' Ho scritto i passi per una stringa di lunghezza 2 e una stringa di lunghezza 3 sotto.

permutazioni ('ab')

len('ab') is not <= 1 
perms = permutations of 'b' 
len('b') <= 1 so return 'b' in a list 
perms = ['b'] 
char = 'a' 
result = [] 
for 'b' in ['b']: 
    for 0 in [0,1]: 
     result.append('' + 'a' + 'b') 
    for 1 in [0,1]: 
     result.append('b' + 'a' + '') 
result = ['ab', 'ba'] 

permutazioni ('abc')

len('abc') is not <= 1 
perms = permutations('bc') 
perms = ['bc','cb'] 
char = 'a' 
result =[] 
for 'bc' in ['bc','cb']: 
    for 0 in [0,1,2]: 
     result.append('' + 'a' + 'bc') 
    for 1 in [0,1,2]: 
     result.append('b' + 'a' + 'c') 
    for 2 in [0,1,2]: 
     result.append('bc' + 'a' + '') 
for 'cb' in ['bc','cb']: 
    for 0 in [0,1,2]: 
     result.append('' + 'a' + 'cb') 
    for 1 in [0,1,2]: 
     result.append('c' + 'a' + 'b') 
    for 2 in [0,1,2]: 
     result.append('cb' + 'a' + '') 
result = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']