3
$\begingroup$

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]
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Patrick87 Nov 27 '13 at 23:58
  • 1
    $\begingroup$ Of course there is a proof. What have you tried and where did you get stuck? Are you familiar with induction? $\endgroup$ – Raphael Dec 4 '14 at 9:21
2
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

Another option, just to show that you can think out of the box. You can prove that:

  1. The algorithm appends exactly factorial(len(l)) permutations to P;
  2. No permutation is appended twice.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.