How does the second element swap in this permutation program work? At which step in the program does the second swap take place? After the first recursion or after all recursion is done?
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
When I leave the second swap out and try A = [2,3,5,7] I get 4! elements, but with repetitions:
[[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]]
With the second swap in place I get the correct 4! elements:
[[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]]
The rule with recursion is (almost always) that you don't let state changes in subproblems mutate parent state. Each call frame shouldn't know or care about what happens in (potentially distant) child calls, preserving recursive self-similarity. The argument data structure should be effectively immutable.
The post-recursive-call swap achieves immutability by performing an undo of the pre-call swap, returning the list back to the way it was before that iteration of the loop. This state restoration is critical for correctness, because without it, the next iteration of the loop (and every one after that) will have a list that had been modified by arbitrary nested child calls on previous iterations, ruining the methodical, enumerative approach of each recursive call frame swapping element at i with every element j, then recursing on the rest of the list starting at i + 1 with 0..i fixed for the remainder of the sub-calls.
To show that the immutability is the key factor and that the undo swap is just a means to achieve that, you can write the algorithm in a way that copies the argument list whenever it's passed as an argument:
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]))
Notice we no longer need to copy when appending to the result because each frame now has a unique list to operate on without concerns of aliasing. This approach incurs a bit more copying overhead than the original approach, though.
This is beside the point, but I'd return a generator for an algorithm like this, as itertools does.