Could anyone explain to me this permutation algo to me? I know it does permutations, but I can not figure out why it works.
s = [1,2,3,4,5,6,7,8,9]
def perm(s, i):
if i == len(s):
print s
for j in range(i, len(s)):
s[i], s[j] = s[j], s[i]
perm(s, i + 1)
s[i], s[j] = s[j], s[i] //why it swaps back?
This function mutates the array s into each possible permutation then prints the permutation and reverses the mutation on the way back out.
At each position i, it leaves all the entries with index less than i alone, tries all later values in position i, and uses recursion to find all permutations with that set of fixed values and each choice for what's at position i. At the highest index, there are no remaining choices, but you've located one of the permutations, so it prints that as a result.
I find it helpful in understanding this sort of recursion to put extra "debug prints" in the code at interesting points like the start and end of the function, and in this case at the swaps.
It's certainly not the most elegant Python (some of the debug prints should be extracted to functions), but running this version of your code with some of these "debug prints" added might be instructive.
def perm(s, i):
print '{padding}starting perm({list}, {index})'.format(list=s, index=i, padding=' '*i)
if i == len(s):
print s
for j in range(i, len(s)):
print '{padding}swapping s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
s[i], s[j] = s[j], s[i]
perm(s, i + 1)
print '{padding}swapping back s[{index1}]={entry1} and s[{index2}]={entry2}'.format(index1=i, entry1=s[i], index2=j, entry2=s[j], padding=' '*i)
s[i], s[j] = s[j], s[i]
print '{padding}returning from perm({list}, {index})'.format(list=s, index=i, padding=' '*i)
it swaps back because it's python code, which means that s (the list) is mutable, so changes made to it in the called function affect the array in the caller.
if it didn't swap back then the array would be in a "strange" state (left by the previous calls) after the call returns.
an alternative, that should not need mutation, is:
s = [1,2,3,4,5,6,7,8,9]
def perm(s, i):
s = list(s) # copy before mutating
if i == len(s):
print s
for j in range(i, len(s)):
s[i], s[j] = s[j], s[i]
perm(s, i + 1)
or, perhaps clearer:
s = [1,2,3,4,5,6,7,8,9]
def perm(s, i):
if i == len(s):
print s
for j in range(i, len(s)):
s[i], s[j] = s[j], s[i]
perm(list(s), i + 1) # pass a copy
