Python DFS, kann nicht herausfinden, warum Rückkehrliste leer ist, wenn append/pop() aber funktioniert für [] + [] in rekursivem Aufruf

Question

kann mir jemand plz sagen, warum dieser Code leere "res" Variable generieren? Wenn Sie die kommentierte Zeile auskommentieren und darunter entfernen, funktioniert alles einwandfrei.

Codes nicht:

class Solution(object): 
    def dfs(self, nums, res, line): 
     if not nums: 
      print(line) 
      res.append(line) 
      return 

     for i, num in enumerate(nums): 
      line.append(num) 
      # self.dfs(nums[:i]+nums[i+1:], res, line+[num]) 
      self.dfs(nums[:i]+nums[i+1:], res, line) 
      line.pop() 

    def permute(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: List[List[int]] 
     """ 
     res = [] 
     self.dfs(nums, res, []) 
     print(res) 
     return res 

if __name__ == "__main__": 
    Solution().permute([1,2]) 

feine Arbeiten, wenn auf veränderte: die DFS für die Weitergabe

for i, num in enumerate(nums): 
    self.dfs(nums[:i]+nums[i+1:], res, line+[num]) 

außer der Verwendung von anhängen/pop. Selbst die "line" Variable vor dem Anhängen an "res" ist korrekt.

Hat das etwas mit Referenzieren zu tun? Das einzige, woran ich denken konnte, ist, was auch immer an Res weitergegeben wurde. Ich würde mich sehr freuen, wenn mir jemand den Link zur Referenz zeigen könnte.

Answer 1

Ihr Tipp ist richtig. Genau wie Java ist die Liste in Python Kopie-für-Verweis. Betrachten Sie das folgende Beispiel:

a = [1, 2, 3] 
b = a 
a.append(4) 
print(b) 

Sie

[1, 2, 3, 4] 

So erhalten, eine einfache Möglichkeit, den Code zu beheben ist, dass anstelle der res.append(line) in dfs() direkt vor der Rückkehr in:

res.append(line[:]) 

Im Grunde erstellt line[:] ein separates Listenobjekt. Sie können weitere Informationen in this thread sehen.

Answer 2

Python Funktionsaufruf Semantik:

• Sind nicht pass-by-reference. Das empfangende Ende braucht es nicht zu referenzieren.

• Sind nicht pass-by-value. Es gibt keine Kopie des Wertes.

• Kann am besten als beschrieben werden, vorbei an Objekt. Das Objekt selbst wird an die Funktion übergeben; nicht eine Referenz, keine Kopie, das eigentliche Objekt selbst.

Siehe Frederik Lundhs article about call by object semantics. Der Wikipedia-Artikel nennt dies "call by sharing" und schreibt Barbara Liskov diesen Begriff zu.

Dies bedeutet, dass jedes Container-Objekt, das Sie als Parameter übergeben, in der Funktion als das gleiche Objekt vorhanden ist und Änderungen dort im Container-Objekt persistent bleiben. Das gleiche gilt für jedes veränderbare Objekt.

Wenn Sie also einen übergebenen Container ändern möchten, ändern Sie ihn nicht direkt. Erstellen Sie eine Kopie (normalerweise durch Aufrufen des Typs, z. B. list, um eine neue Instanz zu erhalten), und ändern Sie diese.

Wenn es der Zweck der Funktion ist, einen neuen Container zu generieren, sollte sie eine eigene Instanz erstellen und return diese Kopie.

Also ich denke, die dfs Funktion ist schlecht entworfen. Es sollte stattdessen etwas tun wie:

def dfs(nums, line): 
    result = [] 

    for i, num in enumerate(nums): 
     line.append(num) 
     result.extend(dfs(nums[:i]+nums[i+1:], line)) 
     line.pop() 
    else: 
     print(line) 
     result.append(line) 

    return result