Does order matter in Python's swap notation? (a, b = b, a)

Question

I've been solving a coding interview problem that looks like:

Given an array of characters, A, and an array of ints, P, where P[i] represents the location of the element at i in the permutation. For example, when A = <a, b, c, d> and P = <2, 0, 1, 3>, A should become <b, c, a, d>

My solution for this looks like:

for i in range(len(A)):
    while perm[i] != i:
        A[i], A[perm[i]] = A[perm[i]], A[i]
        perm[i], perm[perm[i]] = perm[perm[i]], perm[i]

This one gives me an infinite loop while the one below works

for i in range(len(A)):
    while perm[i] != i:
        A[perm[i]], A[i] = A[i], A[perm[i]] 
        perm[perm[i]], perm[i] = perm[i], perm[perm[i]]

I always thought that the order in the swap shortcut in Python does not matter, but I am so confused why the one above does not work and the one below works fine.

Any thoughts?

Answer 1

The order matters a little, and you created code where it ends up mattering. The entire right-hand side is fully computed before any assignment occurs, so in simple scenarios, it doesn't matter. But comparing:

perm[i], perm[perm[i]] = perm[perm[i]], perm[i]

to:

perm[perm[i]], perm[i] = perm[i], perm[perm[i]]

the assignment to perm[i] in the first one affects the value read from perm[i] when assigning to perm[perm[i]]; in the second, the assignment to perm[perm[i]] uses the old value of perm[i] to determine where to assign, then assigns the new value of perm[i].

This happens because assignment is performed left to right; the steps taken, in order are:

1. tuple of all values on right is constructed (no actual tuple is constructed in current interpreter, but that happens logically)
2. Assignment to left target occurs (including all reads necessary to figure out where to assign)
3. Assignment proceeds to right target

Basically, you have a problem because you both read and write the same value on the left hand side of the assignment, in different orders.

Answer 2

Yes, the order matters here, because you are changing the contents of the list perm at indices read from the same list. If the values at the same indices are changing, then assigning in a different order can give a different result.

Here's the bytecode it compiles to: the order is (read, read, read, write, read, write).

>>> dis.dis('perm[i], perm[perm[i]] = perm[perm[i]], perm[i]')
  1           0 LOAD_NAME                0 (perm)
              3 LOAD_NAME                0 (perm)
              6 LOAD_NAME                1 (i)
              9 BINARY_SUBSCR                          # reads from perm
             10 BINARY_SUBSCR                          # reads from perm
             11 LOAD_NAME                0 (perm)
             14 LOAD_NAME                1 (i)
             17 BINARY_SUBSCR                          # reads from perm
             18 ROT_TWO
             19 LOAD_NAME                0 (perm)
             22 LOAD_NAME                1 (i)
             25 STORE_SUBSCR                           # writes to perm
             26 LOAD_NAME                0 (perm)
             29 LOAD_NAME                0 (perm)
             32 LOAD_NAME                1 (i)
             35 BINARY_SUBSCR                          # reads from perm
             36 STORE_SUBSCR                           # writes to perm
             37 LOAD_CONST               0 (None)
             40 RETURN_VALUE

Here's the other way around: the order is (read, read, read, read, write, write).

>>> dis.dis('perm[perm[i]], perm[i] = perm[i], perm[perm[i]]')
  1           0 LOAD_NAME                0 (perm)
              3 LOAD_NAME                1 (i)
              6 BINARY_SUBSCR                          # reads from perm
              7 LOAD_NAME                0 (perm)
             10 LOAD_NAME                0 (perm)
             13 LOAD_NAME                1 (i)
             16 BINARY_SUBSCR                          # reads from perm
             17 BINARY_SUBSCR                          # reads from perm
             18 ROT_TWO
             19 LOAD_NAME                0 (perm)
             22 LOAD_NAME                0 (perm)
             25 LOAD_NAME                1 (i)
             28 BINARY_SUBSCR                          # reads from perm
             29 STORE_SUBSCR                           # writes to perm
             30 LOAD_NAME                0 (perm)
             33 LOAD_NAME                1 (i)
             36 STORE_SUBSCR                           # writes to perm
             37 LOAD_CONST               0 (None)
             40 RETURN_VALUE

So the first one is able to read a value that has been written in the same line, because it has a write followed by a read; but the second one can't, because it does all of its reads before it writes anything.

Honestly, I think you should just not ever write code like this, because even if by sheer luck it does what you want, it's a puzzler - it's not obvious what it should do, let alone what it does do. Declare a variable like j = perm[i] and then write perm[i], perm[j] = perm[j], perm[i], and the code will be understandable and definitely not magic.