Permutation of an array by recursion, when does the second element swap take place?

Question

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]]

This is a bit hard to understand because the recursive function is modifying a mutable data structure. Recursion feels a lot more natural when used with immutable data structures. What happens in the `for`-loop is that we want to try `directed_permutations(i+1)` with every possible element A[j] moved to position A[i]. So, first we try by swapping A[i] and A[i]. Then we undo the swap and try by swapping A[i] and A[i+1]. Then we undo the swap and try by swapping A[i] and A[i+2]. Etc — Stef, Jan 04 '22 at 09:56
@Fortinbras I agree with Stef, recursion is best suited when used against persistent data structures. I think you will find [this Q&A](https://stackoverflow.com/a/70444244/633183) to be helpful. — Mulan, Jan 04 '22 at 19:29

ggorlen · Accepted Answer · 2022-01-04T19:03:17.730

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.

Permutation of an array by recursion, when does the second element swap take place?

1 Answers1