# 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. Nov 27, 2013 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, 2014 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;