String Aşağıdaki kod bir dize için tüm permütasyon üreten

Question

tüm permütasyon almak için bu algoritmayı açıklayınız:

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 

nasıl çalıştığını açıklayabilir misiniz? Özyineyi anlamıyorum.

Answer 1

algoritmadır:

• ilk harfi
• kalan harflerin bütün permütasyon bul (özyinelemeli adım)
• mümkün olan her yerde uzaklaştırıldı mektubu yeniden yerleştirin çıkarın.

Özyineleme için temel durum tek bir harftir. Tek bir harfe izin vermenin tek bir yolu vardır.

başlangıç ​​kelimesi bar olduğunu düşünün örnek çalıştı.

• İlk önce b'u kaldırın.
• ar'un izinlerini bulun. Bu, ar ve ra verir.
bu kelimelerin her biri için
• , her yerde b koyun:
  • ar ->bar, abr, arb
  • ra-bra, rba, rab

Answer 2

Ben> ve bir uzunluk 2 ve bir uzunluk 3 dizesi için adımları yazdı.

permütasyon ('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'] 

permütasyon ('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']