Understading permutations

Question

I was going through this post trying to learn more about permutations: Finding all possible permutations of a given string in python

And I got stuck on this code:

def permutations(string, step = 0):

    # if we've gotten to the end, print the permutation
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):

        # copy the string (store as array)
        string_copy = [character for character in string]

        # swap the current index with the step
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]

        # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
        permutations(string_copy, step + 1)

I'm not understanding the line where we swap the current index with the step, what exactly is this doing? I know that we move to the right once sith step but how does string_copy[step], string_copy[i] = string_copy[i], string_copy[step] aid that? I've just no idea what's happening

Answer 1

a,b = b,a is a Python idiom for swapping two values, it can also be written:

temp = a
a = b
b = temp

Inside the for loop, above permutations(...), add this line:

print "step", step, "index", i, string, "->", string_copy

Now it will show you the inner workings as it runs:

>>> permutations("abc")

step 0 index 0 abc -> ['a', 'b', 'c']
step 1 index 1 ['a', 'b', 'c'] -> ['a', 'b', 'c']
step 2 index 2 ['a', 'b', 'c'] -> ['a', 'b', 'c']
abc
step 1 index 2 ['a', 'b', 'c'] -> ['a', 'c', 'b']
step 2 index 2 ['a', 'c', 'b'] -> ['a', 'c', 'b']
acb
step 0 index 1 abc -> ['b', 'a', 'c']
step 1 index 1 ['b', 'a', 'c'] -> ['b', 'a', 'c']
step 2 index 2 ['b', 'a', 'c'] -> ['b', 'a', 'c']
bac
step 1 index 2 ['b', 'a', 'c'] -> ['b', 'c', 'a']
step 2 index 2 ['b', 'c', 'a'] -> ['b', 'c', 'a']
bca
step 0 index 2 abc -> ['c', 'b', 'a']
step 1 index 1 ['c', 'b', 'a'] -> ['c', 'b', 'a']
step 2 index 2 ['c', 'b', 'a'] -> ['c', 'b', 'a']
cba
step 1 index 2 ['c', 'b', 'a'] -> ['c', 'a', 'b']
step 2 index 2 ['c', 'a', 'b'] -> ['c', 'a', 'b']
cab

1. See whenever the step and index are the same, a character is swapped with itself and nothing changes. So there are fifteen calls to generate six permutations.

I'm finding it hard to make an example that adds any more clarity. How about this:

 # (step, index)

 (0, 0) -- a
    (1, 1) -- ab
       (2, 2) -- abc        # reached the last character, print this!
      <-
    (1, 2) -- ac
       (2, 2) -- acb        # reached the last character, print this!
      <-
   <-
 (0, 1) -- b
    (1, 1) -- ba
       (2, 2) -- bac        # reached the last character, print this!
      <-
    (1, 2) -- bc
       (2, 2) -- bca        # reached the last character, print this!
      <-
   <-
 (0, 2) -- c
    (1, 1) -- cb
       (2, 2) -- cba        # reached the last character, print this!
      <-
    (1, 2) -- ca
       (2, 2) -- cab        # reached the last character, print this!
      <-
   <-

• This shows not just a loop, but a heirarchy, a tree. Things to the right are deeper, they are under things to the left. Beneath them. Inside them. The first part of the pattern is all the things under -- a, the second part is all things under -- b, the third part is all things under -- c.
• Each call to permute() pushes everything -> to the right.
• Each time permute() finishes, we return back <- to the left.
  • Moving right increases the step.
  • Moving down at the same indent increases the index.
  • Moving down and right, increases step and index together.
• Each time we indent -> we take the state from the parent thing. All things under --a start with -- a. All things under -- ab start with -- ab.
• The indenting has 3 left-right positions because the string has 3 characters, a 4 character string gets another level of indent, and therefore a lot more lines - for a lot more permutations.
• It's no coincidence that 'step' number matches how far right the indenting is.

and, to try and answer your comment questions:

• The line for i in range(step, len(string)): starts the index counter from the current indent / step level. That's why it goes from (1,1) to (2,2) at a deeper level. You can see that when we come back from (2,2) we pick up the previous state (1,1) and at the same level go to (1,2), then into (2,2) at a deeper level under there.

• The reason we go from (2,2) back to (0,0) is because we've got to the end of the string by indenting to the right, as many times as we can, until we've run out of permutations starting with 'a'. 'abc' and 'acb' Then we go back to the start, starting with 'b'. 'bac' and 'bca'. Then we've run out, go back to the start.

e.g.

 (0, 0) -- a
    (1, 1) -- ab
       (2, 2) -- abc    #STEP has reached the end of the string, move left

    # We moved left, index was 1 so we've got more work to do
    (1, 2) -- ac
       (2, 2) -- acb    #STEP has reached the end of the string, move left

    # We moved left, index was 2 so that has also reached the end of the string
    # no more work to do inside the group (0,0) -- a, so move left again.
  <- 
  # Now at this far left level, we can change the far left column from (0,0) to (0,1)
  # and then repeat all of the above.

At every level, the same pattern is happening. Change this column/level, and repeat all the lower levels. It's a self-similar, recursive, loopy pattern.

I have 8 versions of print statements in my example code, printing different combinations of things to try and show what's going on. I decided the above is the most clear, but I encourage you to put print statements in and re-run it. Print 'string' and 'string_copy' before and after the swap, print 'string_copy[step:]' and print " "*(3*(step+1)) to print indents.

There's no easy explanation that I know of. There's no substitute for staring at the code, working through it bit by bit over and over until it makes more sense.

Answer 2

This is a nice piece of code. The swap is the step creating a different permutations here. I tried running this with 2 additional print statements like below:

def permutations(string, step = 0):
    print string ############ADDED
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):
        string_copy = [character for character in string]
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]
        print step, i, string_copy ##############ADDED
        permutations(string_copy, step + 1)

permutations("abc")

The result of the run is as below:

• abc
• 0 0 ['a', 'b', 'c']
• ['a', 'b', 'c']
• 1 1 ['a', 'b', 'c']
• ['a', 'b', 'c']
• 2 2 ['a', 'b', 'c']
• ['a', 'b', 'c']
• abc
• 1 2 ['a', 'c', 'b']
• ['a', 'c', 'b']
• 2 2 ['a', 'c', 'b']
• ['a', 'c', 'b']
• acb
• 0 1 ['b', 'a', 'c']
• ['b', 'a', 'c']
• 1 1 ['b', 'a', 'c']
• ['b', 'a', 'c']
• 2 2 ['b', 'a', 'c']
• ['b', 'a', 'c']
• bac
• 1 2 ['b', 'c', 'a']
• ['b', 'c', 'a']
• 2 2 ['b', 'c', 'a']
• ['b', 'c', 'a']
• bca
• 0 2 ['c', 'b', 'a']
• ['c', 'b', 'a']
• 1 1 ['c', 'b', 'a']
• ['c', 'b', 'a']
• 2 2 ['c', 'b', 'a']
• ['c', 'b', 'a']
• cba
• 1 2 ['c', 'a', 'b']
• ['c', 'a', 'b']
• 2 2 ['c', 'a', 'b']
• ['c', 'a', 'b']
• cab

If you observe the first pass returns 'abc' itself as step matches i making the swap trivial. Then b and c get swapped to create acb and so on.