如何高效地在二维矩阵中进行双向移位？

Question

给定一个二维矩阵，例如

l = [[1,1,1],
     [2,5,2],
     [3,3,3]])

如何以最有效的方式在列和行上执行位移操作？

例如：

shift('up', l) 

[[2, 5, 2],
 [3, 3, 3],
 [1, 1, 1]]

但是

shift('left', l) 

[[1, 1, 1],
 [5, 2, 2],
 [3, 3, 3]]

我在两个方向上都使用了collections.deque，因为这个答案，但是对于'向左'或'向右'需要N次转移，而'向上'或'向下'只需要1次转移（我的实现对每一行都使用了一个for循环）。

在C中，我认为可以使用指针算术来改进（例如，参见此答案）。

是否有更好的Pythonic方法？

编辑：

• 通过高效，我指的是如果有一种避免N次转移的方法。
• 我们可以假设矩阵是正方形的。
• 转移可以就地进行。

感谢martineau指出这些问题的重要点。 很抱歉我之前没有指出它们。

- Jorge Leitao

---

在什么方面高效...循环、内存？ - martineau

移位量是否可能大于相应的矩阵维度？如果是，应该发生什么？ - martineau

@martineau 在问题描述的意义上是高效的：它目前需要N次移位，而1次移位是理想的；我考虑的移位量是1，但可以自由泛化；当矩阵的大小为时，Shift是恒等变换。 - Jorge Leitao

如果您在问题中描述了效率类型，我就不需要请求澄清了。这里还有几个问题：矩阵可以假定为方阵吗？该函数是原地移动矩阵还是返回一个新的矩阵？ - martineau

@martineau，你是对的，我很抱歉。我编辑了问题以使其更清晰。 - Jorge Leitao

Answer 1

Numpy提供了一个名为roll()的方法来移动元素。

>>> import numpy as np
>>> x = np.arange(9)
>>> x = x.reshape(3, 3)
>>> print(x)

[[0 1 2]
 [3 4 5]
 [6 7 8]]

>>> x = np.roll(x, -1, axis=0) # up
>>> print(x)

[[3 4 5]
 [6 7 8]
 [0 1 2]]

>>> x = np.roll(x, 1, axis=0) # down
>>> print(x)

[[0 1 2]
 [3 4 5]
 [6 7 8]]

>>> x = np.roll(x, 2, axis=1) # right
>>> print(x)

[[1 2 0]
 [4 5 3]
 [7 8 6]]

>>> x = np.roll(x, -2, axis=1) # left
>>> print(x)    

[[0 1 2]
 [3 4 5]
 [6 7 8]]

我猜Numpy在矩阵操作方面将比大多数解决方案更高效，而且您不会被限制于二维矩阵。

- Nima Mousavi

---

我将此标记为被接受的答案，因为即使没有被证明更快，它肯定更易于维护和符合Python风格。 - Jorge Leitao

@J.C.Leitão：我认为使用第三方库扩展比Python更有效率并不是很_pythonic_……而且你所说的“未被优化为更快”是什么意思？ - martineau

这个问题似乎表明想要一个自己实现的解决方案，尽管标题并没有这样说。不管怎样，使用第三方库怎么就不符合Python风格了呢？ - Nima Mousavi

Answer 2

以下是一种相对高效的方法，适用于非方阵：

DIRS = NONE, UP, DOWN, LEFT, RIGHT = 'unshifted', 'up', 'down', 'left', 'right'

def shift(matrix, direction, dist):
    """ Shift a 2D matrix in-place the given distance of rows or columns in the
        specified (NONE, UP, DOWN, LEFT, RIGHT) direction and return it.
    """
    if dist and direction in (UP, DOWN, LEFT, RIGHT):
        n = 0
        if direction in (UP, DOWN):
            n = (dist % len(matrix) if direction == UP else -(dist % len(matrix)))
        elif direction in (LEFT, RIGHT):
            n = (dist % len(matrix[0]) if direction == LEFT else -(dist % len(matrix[0])))
            matrix[:] = list(zip(*matrix))  # Transpose rows and columns for shifting.

        h = matrix[:n]
        del matrix[:n]
        matrix.extend(h)

        if direction in (LEFT, RIGHT):
            matrix[:] = map(list, zip(*matrix))  # Undo previous transposition.

    return matrix


if __name__ == '__main__':

    # Some non-square test matrices.
    matrix1 = [[1, 2, 3],
               [4, 5, 6],
               [7, 8, 9],
               [10, 11, 12]]

    matrix2 = [[1, 2, 3, 4],
               [5, 6, 7, 8],
               [9, 10, 11, 12]]

    def shift_and_print(matrix, direction, dist):
        GAP =  2  # Plus one for a ":" character.
        indent = max(map(len, DIRS)) + GAP
        print(direction
                + ': ' + (indent-2-len(direction))*' '
                + ('\n'+indent*' ').join(map(str, shift(matrix, direction, dist)))
                + '\n')

    for matrix in matrix1, matrix2:
        for direction in DIRS:
            shift_and_print(matrix, direction, 1)  # Printed results are cumulative.

输出（注意，由于操作是原地执行的，并且移位应用于上一次调用的结果，因此结果是累积的）：

no shift: [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

up:       [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]
          [1, 2, 3]

down:     [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

left:     [2, 3, 1]
          [5, 6, 4]
          [8, 9, 7]
          [11, 12, 10]

right:    [1, 2, 3]
          [4, 5, 6]
          [7, 8, 9]
          [10, 11, 12]

no shift: [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

up:       [5, 6, 7, 8]
          [9, 10, 11, 12]
          [1, 2, 3, 4]

down:     [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

left:     [2, 3, 4, 1]
          [6, 7, 8, 5]
          [10, 11, 12, 9]

right:    [1, 2, 3, 4]
          [5, 6, 7, 8]
          [9, 10, 11, 12]

- martineau

Answer 3

也许可以使用 numpy 来实现类似这样的功能：

def shift(x, direction='up'):
    if direction == 'up':
        temp = range(x.shape[0])
        indicies = temp[1:] + [temp[0]]
        return x[indicies]
    elif direction == 'left':
        temp = range(x.shape[1])
        indicies = temp[1:] + [temp[0]]
        return x[:, indicies]
    else:
        print 'Error direction not known'

结果：

>>> shift(l, direction='up')
array([[2, 5, 2],
       [3, 3, 3],
       [1, 1, 1]])
>>> shift(l, direction='left')
array([[1, 1, 1],
       [5, 2, 2],
       [3, 3, 3]])
>>> shift(l, direction='to the moon')
Error direction not known

- Akavall

Answer 4

这是一个通用版本，您可以将其旋转到四个方向，并且可以进行任意次数的旋转。

l = [[1,1,1],
     [2,5,2],
     [3,3,3]]

def shift(direction, count, myList):
    myLen = len(myList)
    if direction == "up":
        return [myList[i % myLen] for i in range(count, count + myLen)]
    elif direction == "down":
        return [myList[-i] for i in range(count, count - myLen, -1)]
    elif direction == "left":
        tlist = zip(*myList)
        return map(list, zip(*[tlist[i % myLen] for i in range(count, count + myLen)]))
    elif direction == "right":
        tlist = zip(*myList)
        return map(list, zip(*[tlist[-i] for i in range(count, count - myLen, -1)]))

print shift("up", 1, l)
print shift("up", 2, l)
print shift("down", 2, l)
print shift("down", 1, l)
print shift("left", 1, l)
print shift("right", 1, l)

输出

[[2, 5, 2], [3, 3, 3], [1, 1, 1]]
[[3, 3, 3], [1, 1, 1], [2, 5, 2]]
[[2, 5, 2], [3, 3, 3], [1, 1, 1]]
[[3, 3, 3], [1, 1, 1], [2, 5, 2]]
[[1, 1, 1], [5, 2, 2], [3, 3, 3]]
[[1, 1, 1], [2, 2, 5], [3, 3, 3]]

- thefourtheye

---

诚然，这个问题在许多重要的方面上都比较模糊，但是你的代码只适用于方阵 -- 因此它可能不够“通用”。 - martineau