Giải pháp lặp lại cho: - Tìm các hoán vị chuỗi

Question

Tôi đọc this giải pháp trăn đơn giản và thanh lịch để tìm tất cả hoán vị của một chuỗi nhất định. Nó là đệ quy. Dựa trên đó tôi đã cố gắng thực hiện một giải pháp lặp trong python.

Dưới đây là mã của tôi. Nhưng nó chỉ hoạt động cho 3 chuỗi ký tự: (Stuck cố gắng để xem tình trạng trường hợp đệ quy và điều kiện đệ quy chuyển thành lặp đi lặp lại (không đệ quy) Bất kỳ con trỏ nào sẽ giúp có được một giải pháp lặp đi lặp lại (hoặc dựa trên thuật toán này hoặc bất kỳ khác)

def permutations_iter(word): 
while True: 
    perms = [] 
    result = [] 

    char = word[0] 
    new_word = word[1:] 

    if len(new_word)==2: 
     perms = [new_word,''.join(reversed(new_word))] 

    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 

    if len(new_word)==2: 
     break; 


    #example code to call this iterative function   
    print permutations_iter("LSE") 

Answer 1

Bạn có thể chuyển đổi tất cả các đệ quy một lần lặp sử dụng một chồng. Nhưng trong trường hợp này nó thậm chí còn đơn giản hơn kể từ khi thuật toán rất đơn giản.

def perms(word): 
    stack = list(word) 
    results = [stack.pop()] 
    while len(stack) != 0: 
     c = stack.pop() 
     new_results = [] 
     for w in results: 
      for i in range(len(w)+1): 
       new_results.append(w[:i] + c + w[i:]) 
     results = new_results 
    return results 

Đối với một chuyển đổi tổng quát hơn của đệ quy để lặp lại với ngăn xếp đọc this