swapping list variables in nested loop unexpected result (single array?)

Question

If i have a multidimensional array that is a square like this:

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

And I want to turn it 90 degrees clockwise like this:

[[7, 4, 1],
 [8, 5, 2],
 [9, 6, 3]]

I can print out the changed square like this:

for i in range(0,len(a)):
    for j in range(len(a),0,-1):
        print(f"{a[j-1][i]}",end=",")
    print()

The output is:

7,4,1,
8,5,2,
9,6,3,

But if I tried to re-arrange the python list in place, I get the wrong order.

for i in range(0,len(a)):
    x = 0
    for j in range(len(a),0,-1):
        # pythonism to swap w/o temp variable         
        a[i][x],a[j-1][i] = a[j-1][i],a[i][x]
        x += 1
        
print(a)

The output is:

[[3, 6, 1], [8, 5, 2], [9, 4, 7]]
   

To clarify, so far my thinking was that in order to do this we make the following transformation:

a0 a1 a2 => c0 b0 a0
b0 b1 b2 => c1 b1 a1
c0 c1 c2 => c2 b2 a2

Because of the comments I see that the issue was because I am changing the array cells more than once as I move it.

What I am trying to do is change the square not more than using O(1) additional memory. Is there a way to do this without using a new array?

Answer 1

Consider for example the four corner values 1, 3, 7, 9. To accomplish the rotation, 1 must move to where 3 is, 3 to 9, 9 to 7 and 7 to 1 - simultaneously.

Just like how swapping two elements by serial assignment does not work:

a = 1
b = 2
a = b # `a` becomes 2
b = a # oops, `b` doesn't become 1, because this uses the new `a`

similarly the 4-way swap cannot be accomplished by repeated, naive swapping of element pairs:

a, b, c, d = 1, 3, 9, 7 # the values to swap, clockwise around the original
a, b = b, a # put the 1 in the right place
b, c = c, b # oops, moved the 1 again

Regardless of the order in which the swaps are attempted, problems will occur if we do not account for the effect of previous swaps.

The simplest and most understandable way to effect the swap is to just use Python's trick for all four elements at once:

b, c, d, a = a, b, c, d

Given a proper understanding of how the original swap trick works, it is both obvious to try this, and obvious how it works.

In general, an odd-sized square can be decomposed into triangles like so:

aaaaaaaab
caaaaaabb
ccaaaabbb
cccaabbbb
cccc*bbbb
ccccddbbb
cccddddbb
ccddddddb
cdddddddd

and an even-sized square like so:

aaaaaaab
caaaaabb
ccaaabbb
cccabbbb
ccccdbbb
cccdddbb
ccdddddb
cddddddd

So the rotation is simply a matter of setting up loops to iterate over the a region, find the corresponding b/c/d positions for a corresponding a, and doing the swap. This is left as an exercise.

Answer 2

First comment: in your loops, you always loop over range(0, len(a)). This assumes that the height and width are both equal to len(a), in other words this assume that a is a square. However, your task makes sense for all rectangles, not just for squares. So, it is better not to make this assumption. Vertical indices for a should loop over range(0,len(a)), but horizontal indices for a should loop over range(0, len(a[0])).

Second comment: rather than for j in range(len(a),0,-1): print(a[j-1][i],end=","), I recommend for j in range(len(a)-1,-1,-1): print(a[j][i],end=",")

Now on to actually performing the task.

Since your printing-loop works, you can turn it into a function that returns a new list of lists, by "printing into a list", using list.append instead of print. Just replace:

• print(x, end='') with row.append(x);
• print() with result.append(row); row=[]:

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # square
b = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] # non-square rectangle

def rotate_clockwise_append(a):
    height, width = len(a), len(a[0])
    result = []
    row = []
    for i in range(0,width):
        for j in range(height-1,-1,-1):
            row.append(a[j][i])
        result.append(row)
        row = []
    return result

print(rotate_clockwise_append(a)) # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
print(rotate_clockwise_append(b)) # [[9, 5, 1], [10, 6, 2], [11, 7, 3], [12, 8, 4]]

In python, it's always possible to build a list using a list comprehension, rather than using .append in a loop:

def rotate_clockwise_listcomp(a):
    height, width = len(a), len(a[0])
    return [
        [a[j][i] for j in range(height-1,-1,-1)]
        for i in range(0,width)
    ]

print(rotate_clockwise_listcomp(a)) # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
print(rotate_clockwise_listcomp(b)) # [[9, 5, 1], [10, 6, 2], [11, 7, 3], [12, 8, 4]]

You can also use builtin functions to do the reversal operations for you:

def rotate_clockwise_builtin(a):
    return list(zip(*reversed(a)))  # or list(map(list,zip(*reversed(a)))) if you're afraid of a list of tuples

print(rotate_clockwise_builtin(a)) # [(7, 4, 1), (8, 5, 2), (9, 6, 3)]
print(rotate_clockwise_builtin(b)) # [(9, 5, 1), (10, 6, 2), (11, 7, 3), (12, 8, 4)]

If you deal with rectangle arrays a lot, it is often recommended to use numpy rather than builtin python lists:

import numpy as np

def rotate_clockwise_numpy1(a):
    return np.flip(a, axis = 0).T  # flip vertically, then transpose

def rotate_clockwise_numpy2(a):
    return np.flip(np.transpose(a), axis=1)  # transpose, then flip horizontally

print(rotate_clockwise_numpy1(a))
# [[7 4 1]
#  [8 5 2]
#  [9 6 3]]
print(rotate_clockwise_numpy1(b))
# [[ 9  5  1]
#  [10  6  2]
#  [11  7  3]
#  [12  8  4]]

print(rotate_clockwise_numpy2(a))
# [[7 4 1]
#  [8 5 2]
#  [9 6 3]]
print(rotate_clockwise_numpy2(b))
# [[ 9  5  1]
#  [10  6  2]
#  [11  7  3]
#  [12  8  4]]