這個置換程式中的第二個元素交換是如何作業的？第二次交換發生在程式的哪一步？在第一次遞回之后還是在所有遞回完成之后？
def permutations(A: List[int]) -> List[List[int]]:
def directed_permutations(i):
if i == len(A) - 1:
result.append(A.copy())
return
# Try every possibility for A[i]
for j in range(i, len(A)):
A[i], A[j] = A[j], A[i]
# Generate all permutations for A[i 1:]
directed_permutations(i 1)
# Second element swap, which I do not understand
A[i], A[j] = A[j], A[i]
result: List[List[int]] = []
directed_permutations(0)
return result
當我離開第二個交換并嘗試 A = [2,3,5,7] 我得到 4！元素，但有重復：
[[2, 3, 5, 7], [2, 3, 7, 5], [2, 7, 3, 5], [2, 7, 5, 3], [2, 3, 5, 7] , [2, 3, 7, 5], [3, 2, 7, 5], [3, 2, 5, 7], [3, 5, 2, 7], [3, 5, 7, 2] , [3, 2, 7, 5], [3, 2, 5, 7], [5, 2, 3, 7], [5, 2, 7, 3], [5, 7, 2, 3] , [5, 7, 3, 2], [5, 2, 3, 7], [5, 2, 7, 3], [3, 2, 7, 5], [3, 2, 5, 7] , [3, 5, 2, 7], [3, 5, 7, 2], [3, 2, 7, 5], [3, 2, 5, 7]]
隨著第二次交換到位，我得到了正確的 4！要素：
[[2, 3, 5, 7], [2, 3, 7, 5], [2, 5, 3, 7], [2, 5, 7, 3], [2, 7, 5, 3] , [2, 7, 3, 5], [3, 2, 5, 7], [3, 2, 7, 5], [3, 5, 2, 7], [3, 5, 7, 2] , [3, 7, 5, 2], [3, 7, 2, 5], [5, 3, 2, 7], [5, 3, 7, 2], [5, 2, 3, 7] , [5, 2, 7, 3], [5, 7, 2, 3], [5, 7, 3, 2], [7, 3, 5, 2], [7, 3, 2, 5] , [7, 5, 3, 2], [7, 5, 2, 3], [7, 2, 5, 3], [7, 2, 3, 5]]
uj5u.com熱心網友回復：
遞回的規則是（幾乎總是）你不要讓子問題中的狀態變化改變父狀態。每個呼叫框架不應該知道或關心在（可能遙遠的）子呼叫中發生了什么，從而保持遞回自相似性。引數資料結構應該是有效的不可變的。
遞回呼叫后交換通過執行呼叫前交換的撤消來實作不變性，將串列回傳到回圈迭代之前的狀態。這種狀態恢復對于正確性至關重要，因為沒有它，回圈的下一次迭代（以及之后的每一次迭代）將有一個串列，該串列已被先前迭代的任意嵌套子呼叫修改，從而破壞了每個回圈的有條不紊的、列舉的方法遞回呼叫框架在交換元素i與每一個元素j，然后在串列的其余部分遞回開始i 1有0..i固定的子呼叫的剩余部分。
為了證明不變性是關鍵因素并且撤消交換只是實作這一點的一種手段，您可以撰寫演算法，以便在作為引數傳遞時復制引數串列：
from typing import List
def permutations(A: List[int]) -> List[List[int]]:
result = []
def directed_permutations(A, i=0):
if i == len(A) - 1:
result.append(A)
else:
for j in range(i, len(A)):
B = A[:]
B[i], B[j] = B[j], B[i]
directed_permutations(B, i 1)
directed_permutations(A)
return result
if __name__ == "__main__":
print(permutations([1, 2, 3]))
請注意，我們在附加到結果時不再需要復制，因為現在每個幀都有一個唯一的串列可以操作，而無需擔心混疊。但是，這種方法比原始方法產生了更多的復制開銷。
這是題外話，但我會為這樣的演算法回傳一個生成器，就像這樣itertools。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/405890.html
標籤：