Every ordering of 1, 2, 3. Fix position 0 by swapping each element into it in turn, recurse on the rest, and swap back so the next choice starts from the same array. Every leaf is one permutation: 3! = 6 of them.
Generating all permutations of 3 values by swapping each candidate into each position.
Position 0: keep 1 where it is and fix it. Recurse on positions 1 onward.
Position 0 takes 1.
Position 1: keep 2 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 2.
Position 2: keep 3 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 3.
Every position is fixed: a leaf. Permutation 1: 1 2 3.
Leaf. Permutation 1 is 1 2 3.
Back at position 1. Nothing to undo for 2. Try the next candidate.
Undo the swap at position 1.
Position 1: swap 3 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 3.
Position 2: keep 2 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 2.
Every position is fixed: a leaf. Permutation 2: 1 3 2.
Leaf. Permutation 2 is 1 3 2.
Back at position 1. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Nothing to undo for 1. Try the next candidate.
Undo the swap at position 0.
Position 0: swap 2 in from position 1 and fix it. Recurse on positions 1 onward.
Position 0 takes 2.
Position 1: keep 1 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 1.
Position 2: keep 3 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 3.
Every position is fixed: a leaf. Permutation 3: 2 1 3.
Leaf. Permutation 3 is 2 1 3.
Back at position 1. Nothing to undo for 1. Try the next candidate.
Undo the swap at position 1.
Position 1: swap 3 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 3.
Position 2: keep 1 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 1.
Every position is fixed: a leaf. Permutation 4: 2 3 1.
Leaf. Permutation 4 is 2 3 1.
Back at position 1. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Swap 2 back out so the array is as it was, then try the next candidate.
Undo the swap at position 0.
Position 0: swap 3 in from position 2 and fix it. Recurse on positions 1 onward.
Position 0 takes 3.
Position 1: keep 2 where it is and fix it. Recurse on positions 2 onward.
Position 1 takes 2.
Position 2: keep 1 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 1.
Every position is fixed: a leaf. Permutation 5: 3 2 1.
Leaf. Permutation 5 is 3 2 1.
Back at position 1. Nothing to undo for 2. Try the next candidate.
Undo the swap at position 1.
Position 1: swap 1 in from position 2 and fix it. Recurse on positions 2 onward.
Position 1 takes 1.
Position 2: keep 2 where it is and fix it. Recurse on positions 3 onward.
Position 2 takes 2.
Every position is fixed: a leaf. Permutation 6: 3 1 2.
Leaf. Permutation 6 is 3 1 2.
Back at position 1. Swap 1 back out so the array is as it was, then try the next candidate.
Undo the swap at position 1.
Back at position 0. Swap 3 back out so the array is as it was, then try the next candidate.
Undo the swap at position 0.
6 permutations: 1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 2 1 | 3 1 2. Each level of the recursion has one fewer candidate, so the leaves number 3!, and every swap was undone: 10 swaps, the array ends as it began.
6 permutations were generated.