Nicht nachvollziehbar, warum Stringpermutationen in einer globalen Variablen für Arraypermutationen nicht angehängt werden.

Question

Ich versuche, das Stringpermutationsproblem zu codieren. Anstelle von String habe ich eine Liste von ganzen Zahlen wie [1,2,3]. Ich muss alle möglichen Permutationen der Liste ausdrucken. Es gibt jedoch ein Problem mit meinem Code, das ich nicht herausfinden kann. Irgendwie trifft die Zeile if not in words im Base Case nur einmal. Ich versuche das aus der letzten Stunde herauszufinden. Jede Hilfe wäre willkommen! TIA Hier ist der Code

words = list() 
def permute(nums): 
    if len(nums) == 0: 
     return None 

    l = 0 
    r = len(nums) 

    permute_helper(nums,0,r) 

def permute_helper(nums,start,end): 
    current = 0 
    if start == end-1: 
     if not nums in words: 
      print 'appended' 
      words.append(nums) 
    else: 
     for current in range(start,end): 
      temp = nums[start] 
      nums[start] = nums[current] 
      nums[current] = temp 
      #Recursive call 
      permute_helper(nums,start+1,end) 
      temp = nums[start] 
      nums[start] = nums[current] 
      nums[current] = temp 

permute([1,2,3]) 
print words 

Answer 1

Der Fehler ist, dass Sie die gleiche Liste halten modifizieren nums, so dass Sie mit nur einer Kopie am Ende, die geändert wurde, aber die Änderungen wurden nicht aufgezeichnet.

Wechsel:

words.append(nums) 

zu:

words.append(nums[:]) 

, die eine Kopie von nums schaffen und "einzufrieren" es aktuellen Zustand.

Kommentar: Sie den Swap in einer pythonic Weise tun können, statt:

temp = nums[start] 
nums[start] = nums[current] 
nums[current] = temp 

tun:

nums[start], nums[current] = nums[current], nums[start] 

Answer 2

Sie sind Anfügen der gleichen Liste jedes Mal. Kein Wunder, dass es schon da ist (in words).

Mit anderen Worten, Sie sammeln nicht jede einzelne Permutation, sondern einen Verweis auf nums. Folglich werden nachfolgende Permutationen in words widergespiegelt. Das ist die Plage der Wandlungsfähigkeit.

Eine Lösung, die eine Kopie der aktuellen Permutation zu machen ist:

words.append(nums[:]) 

By the way, ein pythonic Swap ist:

a, b = b, a # no need for tmp 

Auch ist es nicht erforderlich, current zurückgesetzt werden.