CODEWITHSUNDEEP
python
kaiserasif
kaiserasif

Reputation: 157

List value swapping: What's the correct order and why?

For a list of integers, such as A = [2, 10, -5], I get the error

Traceback (most recent call last):
  File "so.py", line 6, in <module>
    v, A[v-1] = A[v-1], v
IndexError: list assignment index out of range

Code:

for i, v in enumerate(A):
    while 1<=v<=len(A) and v != A[v-1]:
        v, A[v-1] = A[v-1], v

but this works:

for i, v in enumerate(A):
    while 1<=v<=len(A) and v != A[v-1]:
        A[v-1], v = v, A[v-1]

Why the order of the swapping elements matters here? v is always being checked to be in bound.

Weirdly enough cannot reproduce a smaller example. But, A = [6, 5, 4, 3, 2] becomes an infinite loop.

Upvotes: 2

Views: 184

Answers (3)

vaer-k
vaer-k

Reputation: 11753

A = [6, 5, 4, 3, 2]

for i, v in enumerate(A):
    while 1<=v<=len(A) and v != A[v-1]:
        v, A[v-1] = A[v-1], v

You need to try running out your algorithm in your head:

Start:

i = 0, v = 6

v(6) is not between 1 and 5: next iteration

i = 1, v = 5, A[5-1] = 2

5 is between 1 and 5; v is not equal to 2: swap -> v = 2; A[4] = 2

i = 1, v = 2, A[2-1] = 5

2 is between 1 and 5; v is not equal to 5: swap -> v = 5; A[1] = 5

i = 1, v = 5, A[5-1] = 2

5 is between 1 and 5; v is not equal to 2: swap -> v = 2; A[4] = 2

i = 1, v = 2, A[2-1] = 5

2 is between 1 and 5; v is not equal to 5: swap -> v = 5; A[1] = 5

... and on and on

I don't think your algorithm makes sense. It's unclear why you are using the values in your list to index the list during your loop. I think this confusion about the index and values is at the root of your problem.

Upvotes: 0

Prune
Prune

Reputation: 77867

I reproduced this with [2, 10, -5]. The detailed sequence of operations is

i, v = 0, 2
1 <= 2 ?     OK
2 != A[1] ?  OK ... stay in loop
    v, A[v-1] = 10, 2
    # This assignment breaks into ...
    v = 10
    A[10-1] = 2
    # ... and this second assignment is out of range.

If you switch the assignment order:

    A[v-1], v = 2, 10
    # This assignment breaks into ...
    A[2-1] = 2
    v = 10

In this case, your while conditions have properly guarded a legal assignment.

Note that you are not swapping list values; v is a local variable; it is not a reference to A[i]. For instance, in the above example, you do get v=10, but this does not affect the value of A[0].

Upvotes: 2

Tim
Tim

Reputation: 2843

Python swaps the variables in the order provided, so v is assigned the value at A[v-1], and then tries to reassign A[v-1] - but since v has been modified to be a list element, v-1 is out of range of A.

Upvotes: 7

Related Questions