# Is there a proof of the recursive algorithm for generating all permutations of a sequence?

For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible orderings of the elements will be reached, and/or that no ordering will be duplicated.

For example, what if the elements at index 0 and 1 are swapped, then 1 and 2 are swapped? How does the algorithm guarantee this won't result in a duplicate ordering?

P = []
def permute(l, n=0):
if n == len(l):
return P.append(list(l))
for i in xrange(n, len(l)):
l[i], l[n] = l[n], l[i]
permute(l, n+1)
l[i], l[n] = l[n], l[i]

• Recursive calls to permute only affect areas to the right of the most recently swapped symbol. If the original list doesn't contain duplicates, this cannot produce a duplicate ordering. If the original list does contain duplicates, this algorithm clearly generates them. If Python doesn't show the duplicates, it's because the code is not what you present. – Patrick87 Nov 27 '13 at 23:58
• Of course there is a proof. What have you tried and where did you get stuck? Are you familiar with induction? – Raphael Dec 4 '14 at 9:21

Hint: Prove by induction that $\mathrm{permute}(l,n)$:
• Adds to $P$ all permutations obtained from $l$ by permuting coordinates $n,\ldots,|l|$.
• Leaves $l$ unchanged. That is, the value of $l$ after running the function is the same as its value before running it.
1. The algorithm appends exactly factorial(len(l)) permutations to P;