What happens in degenerate case of multiple assignment?

Question

I'm teaching myself algorithms. I needed to swap two items in a list. Python makes all things easy:

def swap(A, i, j):
    A[i], A[j] = A[j], A[i]

This works a treat:

>>> A = list(range(5))
>>> A
[0, 1, 2, 3, 4]
>>> swap(A, 0, 1)
>>> A
[1, 0, 2, 3, 4]

Note the function is resilient to the degenerate case i = j. As you'd expect, it simply leaves the list unchanged:

>>> A = list(range(5))
>>> swap(A, 0, 0)
>>> A
[0, 1, 2, 3, 4]

Later I wanted to permute three items in a list. I wrote a function to permute them in a 3-cycle:

def cycle(A, i, j, k):
    A[i], A[j], A[k] = A[j], A[k], A[i]

This worked well:

>>> A = list("tap")
>>> A
['t', 'a', 'p']
>>> cycle(A, 0, 1, 2)
>>> A
['a', 'p', 't']

However I (eventually) discovered it goes wrong in degenerate cases. I assumed a degenerate 3-cycle would be a swap. So it is when i = j, cycle(i, i, k) ≡ swap(i, k):

>>> A = list(range(5))
>>> cycle(A, 0, 0, 1)
>>> A
[1, 0, 2, 3, 4]

But when i = k something else happens:

>>> A = list(range(5))
>>> sum(A)
10
>>> cycle(A, 1, 0, 1)
>>> A
[1, 1, 2, 3, 4]
>>> sum(A)
11

What's going on? sum should be invariant under any permutation! Why does this case i = k degenerate differently?

How can I achieve what I want? That is a 3-cycle function that degenerates to a swap if only 2 indices are distinct cycle(i, i, j) ≡ cycle(i, j, i) ≡ cycle(i, j, j) ≡ swap(i, j)

Answer 1

cycle is doing exactly what you ask it to: assigning to the left hand values the right hand values.

def cycle(A, i, j, k):
    A[i], A[j], A[k] = A[j], A[k], A[i]

is functionally equivalent to

def cycle(A, i, j, k):
    new_values = A[j], A[k], A[i]
    A[i], A[j], A[k] = new_values

So when you do cycle(A, 1, 0, 1) what you are saying is that you want

A[1] = previous_A[0]
A[0] = previous_A[1]
A[1] = previous_A[1]

If you want cycle to work sequentially then you must write it sequentially, otherwise python evaluates the right hand and then expands that to the arguments on the left hand.

Answer 2

Well it seems you are re-assigning to the same target A[1], to get a visualization of the call:

A[1], A[0], A[1] = A[0], A[1], A[1]

Remember, from the documentation on assignment statements:

An assignment statement evaluates the expression list (remember that this can be a single expression or a comma-separated list, the latter yielding a tuple) and assigns the single resulting object to each of the target lists, from left to right.

So your evaluation goes something like dis:

• Create tuple with values A[0], A[1], A[1] translating to (0, 1, 1)
• Assign these to the target list A[1], A[0], A[1] from left to right.

Assignment from left to right takes place:

1. A[1] = 0
2. A[0] = 1
3. A[1] = 1

So the first assignment made is A[1] with the first element of the tuple 0, then the second assignment A[0] with the second element 1 and, finally, at the end, A[1] is overriden with the third element in the tuple 1.

---

You can get a more convoluted view of this with dis.dis; notice how all elements in the right hand of the assignment statement are loaded first and then they are assigned to their values:

dis.dis(cycle)
  2           0 LOAD_FAST                0 (A)
              3 LOAD_FAST                2 (j)
              6 BINARY_SUBSCR
              7 LOAD_FAST                0 (A)
             10 LOAD_FAST                3 (k)
             13 BINARY_SUBSCR
             14 LOAD_FAST                0 (A)
             17 LOAD_FAST                1 (i)
             20 BINARY_SUBSCR                   # Loading Done
             21 ROT_THREE
             22 ROT_TWO
             23 LOAD_FAST                0 (A)  # Assign first
             26 LOAD_FAST                1 (i)
             29 STORE_SUBSCR
             30 LOAD_FAST                0 (A)  # Assign second
             33 LOAD_FAST                2 (j)
             36 STORE_SUBSCR
             37 LOAD_FAST                0 (A)  # Assing third
             40 LOAD_FAST                3 (k)
             43 STORE_SUBSCR
             44 LOAD_CONST               0 (None)
             47 RETURN_VALUE