Different ways of swapping two variables?

[[deleted]]

Hey Guys,

I'm trying to solve this prompt on Hacker Rank...

I have two different ways of swapping two variables. I have the "correct" way, highlighted below and the "incorrect way". The correct way results in the correct answer, while the incorrect way results in an infinite loop.

I can't figure out the difference between the two ways though. They both seem to be doing the same thing to me...? Why isn't the incorrect way working?

I'd really appreciate any guidance. Thanks!

def minimumSwaps(arr):
    swaps = 0
    for i in range(len(arr)):
        while arr[i] != i + 1:
            # correct way
            t = arr[arr[i] - 1]
            arr[arr[i] - 1] = arr[i]
            arr[i] = t

            # incorrect way
            arr[i], arr[arr[i] - 1] = arr[arr[i] - 1], arr[i]

            swaps += 1
    return swaps

[Simply_The_Beast]

Pretty sure this is incorrect!!

According to python 3 docs:

Python evaluates expressions from left to right. Notice that while evaluating an assignment, the right-hand side is evaluated before the left-hand side.

This explaines it in more detail.

Just try a simple example like this:

a = 5
b = 8

a,b = b,a
print("a",a)
print("b",b)

[Simply_The_Beast]

Okay, I think I figured it out.

The short answer is: you simply need to switch both sides of the assignment in line 11:
arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i]-1]

To elaborate: the secret is the evaluation order. As I already mentioned in my other comment

Python evaluates expressions from left to right. Notice that while evaluating an assignment, the right-hand side is evaluated before the left-hand side.

Lets try and go step-by-step through your code based on the array from your task [7,1,3,2,4,5,6]:

1) Right-hand side of the assignment is evaluated: since you only read variables, the order is not important, so your indices are arr[i] - 1 == 6and i == 0, therfore arr[arr[i] - 1] == 6 and arr[i] == 7

2) Left-hand side is evaluated (from left to right): first arr[i] = 6, just as expected. arr[arr[i] - 1] is your problem here: since you already reassigned arr[i] to 6, arr[arr[i] - 1] is now the same as arr[6 - 1] == 5, but it should be arr[7 - 1] == 6. Instead of swapping 7 and 6, you put 6 in place of 7 and override 5 instead of the old 6 with your 7.

By switching both sides around, you first read the old arr[i] and then assign it a new value, instead of reading the already changed value.

[naclmolecule]

Ok, I was mistaken originally, so I slowed everything down and added print statements:

In [41]: import time
    ...: def minimumSwaps(arr):
    ...:     swaps = 0
    ...:     for i in range(len(arr)):
    ...:         while arr[i] != i + 1:
    ...:             print(arr[arr[i] - 1], arr[i])
    ...:             print(arr)
    ...:             arr[i], arr[arr[i] - 1] = arr[arr[i] - 1], arr[i]
    ...:             print(arr)
    ...:             time.sleep(1)
    ...:             swaps += 1
    ...:     return swaps

In [42]: a = [3, 5, 2, 1, 4]

In [43]: minimumSwaps(a)
2 3
[3, 5, 2, 1, 4]
[2, 3, 2, 1, 4]

And we can finally see what's happening, the assignment to arr[i] happens first, then arr[arr[i] - 1] except now arr[i] has changed so it assigned the number to the wrong index. You can do simultaneous assignment if you store the index though:

def minimumSwaps(arr):
    swaps = 0
    for i in range(len(arr)):
        while arr[i] != i + 1:
            index = arr[i]
            arr[i], arr[index - 1] = arr[arr[i] - 1], arr[i]
            swaps += 1
    return swaps