用Ruby将矩阵逆时针旋转n个位置

Question

用Ruby将矩阵逆时针旋转n个位置

arraysrubyalgorithmmultidimensional-arraytraversal

5

给定一个二维矩阵：

matrix = [
   [  1,   2,   3,   4  ],
   [  5,   6,   7,   8  ],
   [  9,  10,  11,  12  ],
   [ 13,  14,  15,  16  ]
]

我们如何将矩阵逆时针旋转，使得值被推动到这样的位置？

matrix = [
   [  2,   3,   4,   8  ]
   [  1,   7,  11,  12  ]
   [  5,   6,  10,  16  ]
   [  9,  13,  14,  15  ]
]

注意

这个问题和this和this不是重复的，因为我试图实现的是逆时针旋转值。

我的当前实现和问题

我的当前实现只以逆时针的方式打印出值，但它并没有旋转值。

  layers = [_rows, _cols].min / 2
  r1, r2, c3, c4 = 0, _rows, _cols, _cols
  new_matrix = Array.new(_rows + 1) { Array.new(_cols + 1) }
  (0..layers).each do |layer|
    row_top_left, row_bottom_left,  col_top_right, col_bottom_right = r1, r2, c3, c4
    result = []

    while row_top_left < row_bottom_left
      result << matrix[row_top_left][layer]
      row_top_left += 1
    end

    row_bottom_left = layer
    while row_bottom_left < col_bottom_right
      result << matrix[row_top_left][row_bottom_left]
      row_bottom_left += 1
    end

    temp_col_bottom_right = col_bottom_right
    temp_col_top_right = layer
    while col_bottom_right > temp_col_top_right
      result << matrix[col_bottom_right][temp_col_bottom_right]
      col_bottom_right -= 1
    end

    # p row_top_left
    tmp_row_top_left = layer
    while col_top_right > tmp_row_top_left
      result << matrix[tmp_row_top_left][col_top_right]
      col_top_right -= 1
    end
    p result.cycle



    r1 += 1
    r2 -= 1
    c3 -= 1
    c4 -= 1

更新 v0.1

关键思想是需要以正确的方式旋转矩阵。例如，假设我们的矩阵需要旋转2次。因此：

   matrix_rotation(
       matrix.length - 1,      # rows
       matrix[0].length - 1,   # columns
       2,                      # Nom. of rotation
       matrix                  # The matrix
   )

matrix = [ 
   #   Original               Iter: 1             Iter: 2  
  [ 1,   2,  3,  4 ],  # [ 2,  3,  4,  8 ]  # [ 3,  4,  8, 12 ]
  [ 5,   6,  7,  8 ],  # [ 1,  7, 11, 12 ]  # [ 2, 11, 10, 16 ]
  [ 9,  10, 11, 12 ],  # [ 5,  6, 10, 16 ]  # [ 1,  7,  6, 15 ]
  [ 13, 14, 15, 16 ]   # [ 9, 13, 14, 15 ]  # [ 5,  9, 13, 14 ]
]

更新 v0.2

数组的维度用NxM表示，其中N和M可以是任何数字，偶数或奇数。例如5x4、4x4、4x8等。

不存在"空方块"这样的东西。

- Jamy

1

内部元素没有旋转？ - tokland

1

@Jamy，请纠正所需输出的第一个示例。 - Aleksei Matiushkin

完成 :) @AlekseiMatiushkin - Jamy

为什么你一开始不告诉我们这是一个Hackerrank问题呢？读者，包括我自己，浪费了很多时间试图弄清楚你到底想做什么。如果你给我们提供了Hackerrank问题的链接，所有这些都可以避免。因为链接是明确无误的。 - Cary Swoveland

@iGian 另外提供了一个解决方案，已经修复了这个问题。请查看参考。 - Jamy

显示剩余3条评论

4个回答

3

简短总结

如果您想直接跳转到解决方案代码，请跳转到本答案底部的相应部分。

说明

您需要分解问题并分别解决每个问题。

问题

获取层数
以反向螺旋形式循环，仅获取预期值
根据给定的旋转参数进行位移

让我们逐个点进行说明：

获取层数

您需要一种方法来获取层数。下面的矩阵有2层。如何算出？

假设有一个矩阵：

       matrix           layers
  --------------------------------
 |  1,  2,  3,  4  |   0  0  0  0 |
 |  5,  6,  7,  8  |   0  1  1  0 |
 |  9, 10, 11, 12  |   0  1  1  0 |
 | 13, 14, 15, 16  |   0  0  0  0 |
  --------------------------------

要找到层数，只需执行以下操作：

[rows, cols].min / 2

第一个问题解决了。

倒螺旋形式循环，仅获得期望值

这部分需要很多思考。让我们进行可视化：

       matrix           layers
  --------------------------------
 |  1,  2,  3,  4  |   ↓  ←  ←  ↰ |   0  0  0  0 |
 |  5,  6,  7,  8  |   ↓  1  1  ↑ |   0  ↓  ↰  0 |
 |  9, 10, 11, 12  |   ↓  1  1  ↑ |   0  ↳  →  0 |
 | 13, 14, 15, 16  |   ↳  →  →  → |   0  0  0  0 |
  --------------------------------

这是可以实现的。我们将有4个for循环。每个循环将负责：

左侧（从上到下）
底部（从左到右）
右侧（从下到上）
顶部（从右到左）

在我进入循环之前，我们需要一些容器来以螺旋形式存储值。

让我们有一个临时数组来存储这些值：

# this array will get us the output of borders of the layer
row = []

为了说明，让我们只处理最外层（即第0层）。

第一次循环（左侧：从上到下）

# this loop will output the top-left side of the matrix
# ==============================
#  ↓ [  1,  2,  3,  4 ]
#  ↓ [  5,  6,  7,  8 ]
#  ↓ [  9, 10, 11, 12 ]
#  ↓ [ 13, 14, 15, 16 ]
# Output: [[1, 5, 9], [6] ]
# ==============================
(0...rows - 1 - layer).each do |i|
  row << matrix[i][layer]
end

注意: 0 表示第0层。

第二轮循环（底部：从左到右）

# this loop will output the bottom side of the matrix
# ==============================
#  ↓ [  1,  2,  3,  4 ]
#  ↓ [  5,  6,  7,  8 ]
#  ↓ [  9, 10, 11, 12 ]
#  ↓ [ 13, 14, 15, 16 ]
#   ↪ →   →   →    →
# Output: [[1, 5, 9, 13, 14, 15], [6, 10]]
# ==============================
(0...cols - 1 - layer).each do |i|
  row << matrix[rows - 1 - layer][i]
end

第三次循环（从右到上）

# this loop will output the right side of the matrix
# ==============================
#  ↓ [  1,  2,  3,  4 ] ↑
#  ↓ [  5,  6,  7,  8 ] ↑
#  ↓ [  9, 10, 11, 12 ] ↑
#    [ 13, 14, 15, 16 ] ↑
#   ↪  →   →   →   →  ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8], [6, 10, 11]]
# ==============================
(rows - 1 - layer).step(0 + 1, -1).each do |i|
  row << matrix[i][cols - 1 - layer]
end

第4次循环（从右到左）

# this loop will output the top side of the matrix
# ==============================
#       ←   ←   ←   ←   ↰
#  ↓ [  1,  2,  3,  4 ] ↑
#  ↓ [  5,  6,  7,  8 ] ↑
#  ↓ [  9, 10, 11, 12 ] ↑
#    [ 13, 14, 15, 16 ] ↑
#   ↪  →   →   →   →  ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2], [6, 10, 11, 7]]
# ==============================
(cols - 1 - layer).step(0 + 1, -1).each do |i|
  row << matrix[layer][i]
end

根据给定的旋转参数进行移位

现在，我们已经将数值以螺旋形式呈现出来。但是这个问题最重要的方面在于如何移动这些数值。有趣的是，我们将使用模运算。

模运算在这里起到了关键作用。它将允许我们基于旋转来移动值。同时也会给出正确的数组索引以开始移位。例如，如果我们想要旋转两次：2 % 12 = 2 对于最外层。

# row = [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
shift = rotate % row.size
# if we negate shift variable, we can get correct index
# i.e. row[-2] = 3
idx = -shift

在我们移动数值之前，让我们创建另一个矩阵来包含正确的数值：

 # let us create a new matrix
 result = (1..( rows * cols )).each_slice(rows).to_a

我们将以相同的方式再次循环，但从row的idx获取值。例如：

(0...rows - 1 - 0).each do |i|
  result[i][layer] = row[idx]
  idx += 1
  idx %= row.size
end
(0...cols - 1 - 0).each do |i|
  result[rows - 1 - 0][i] = row[idx]
  idx += 1
  idx %= row.size
end
(rows - 1 - 0).step(0 + 1, -1).each do |i|
  result[i][cols - 1 - 0] = row[idx]
  idx += 1
  idx %= row.size
end
(cols - 1 - 0).step(0 + 1, -1).each do |i|
  result[0][i] = row[idx]
  idx += 1
  idx %= row.size
end

注意: 0 表示第 0 层（为了方便解释）

解决方案

matrix_4_x_4 = (1..16).each_slice(4).to_a

matrix_8_x_8 = (1..64).each_slice(8).to_a

def matrix_rotation(*args)

  # let us extract rows & cols from our matrix. We also need to know how
  # times to rotate.
  rows, cols, rotate, matrix = args

  # to find out how many layers our matrix have, simply get the min of the two (rows, cols)
  # and divide it
  layers, str_cols = [rows, cols].min / 2, ""

  # needed to beatify our console output in table format
  cols.times do str_cols << "%5s " end

  # we will work on a temporary array
  temp_rows = []

  # so the first task is to loop n times, where n is the number of layers
  (0...layers).each do |layer|

    # this array will get us the output of borders of the layer
    row = []

    # this loop will output the top-left side of the matrix
    # ==============================
    #  ↓ [  1,  2,  3,  4 ]
    #  ↓ [  5,  6,  7,  8 ]
    #  ↓ [  9, 10, 11, 12 ]
    #  ↓ [ 13, 14, 15, 16 ]
    # Output: [[1, 5, 9], [6] ]
    # ==============================
    (layer...rows - 1 - layer).each do |i|
      row << matrix[i][layer]
    end

    # this loop will output the bottom side of the matrix
    # ==============================
    #  ↓ [  1,  2,  3,  4 ]
    #  ↓ [  5,  6,  7,  8 ]
    #  ↓ [  9, 10, 11, 12 ]
    #  ↓ [ 13, 14, 15, 16 ]
    #   ↪ →   →   →    →
    # Output: [[1, 5, 9, 13, 14, 15], [6, 10]]
    # ==============================
    (layer...cols - 1 - layer).each do |i|
      row << matrix[rows - 1 - layer][i]
    end

    # this loop will output the right side of the matrix
    # ==============================
    #  ↓ [  1,  2,  3,  4 ] ↑
    #  ↓ [  5,  6,  7,  8 ] ↑
    #  ↓ [  9, 10, 11, 12 ] ↑
    #    [ 13, 14, 15, 16 ] ↑
    #   ↪  →   →   →   →  ⤻
    # Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8], [6, 10, 11]]
    # ==============================
    (rows - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[i][cols - 1 - layer]
    end

    # this loop will output the top side of the matrix
    # ==============================
    #       ←   ←   ←   ←   ↰
    #  ↓ [  1,  2,  3,  4 ] ↑
    #  ↓ [  5,  6,  7,  8 ] ↑
    #  ↓ [  9, 10, 11, 12 ] ↑
    #    [ 13, 14, 15, 16 ] ↑
    #   ↪  →   →   →   →  ⤻
    # Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2], [6, 10, 11, 7]]
    # ==============================
    (cols - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[layer][i]
    end
    temp_rows << row
  end

  # let us create a new matrix
  result = (1..( rows * cols )).each_slice(rows).to_a

  # we're going to loop in the same manner as before
  (0...layers).each do |layer|

    # based on current layer, get the values around that layer
    row = temp_rows[layer]

    # !important: the modulo will do the main thing here:
    # It will allow us to shift values based on the rotate. But also
    # gives us the correct index in the array to start the shift.
    # For example, if we want to rotate 2 times: 2 % 12 = 2 for the outer most layer
    shift = rotate % row.size

    # when whe negate the shift value, we will get the correct index from the end of the array.
    # row = [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
    # So -2 in row[-2] for the outer layer is 3. We increment idx, then row[-1] is 2 etc..
    idx = -shift

    (layer...rows - 1 - layer).each do |i|
      result[i][layer] = row[idx]
      idx += 1
      idx %= row.size
    end
    (layer...cols - 1 - layer).each do |i|
      result[rows - 1 - layer][i] = row[idx]
      idx += 1
      idx %= row.size
    end
    (rows - 1 - layer).step(layer + 1, -1).each do |i|
      result[i][cols - 1 - layer] = row[idx]
      idx += 1
      idx %= row.size
    end
    (cols - 1 - layer).step(layer + 1, -1).each do |i|
      result[layer][i] = row[idx]
      idx += 1
      idx %= row.size
    end
  end

  result.each do |row| printf("#{str_cols}\n", *row) end

end

matrix_rotation(
  matrix_8_x_8.size,
  matrix_8_x_8.first.size,
  2,
  matrix_8_x_8
)

- nas.engineer

非常感谢。我首先需要测试您的代码以查看它是否实际有效。太棒了。我现在要仔细阅读它 :) - Jamy

0

这是另一种实现方式（我没有创建一个方法，只是需要改进的逻辑）。

array = (1..24).each_slice(6).to_a
array.each { |e| p e }
puts 

n = 4 # sub matrix rows
m = 6 # sub matrix cols
x = 0 # x row origin (corner) of the rotation
y = 0 # y col origin (corner) of the rotation
rotations = 2 # negative is ccw, positive is cw

raise "Sub matrix too small, must be 2x2 at least" if m < 2 || n < 2
# to add: check if the submatrix is inside the matrix, given the origin x, y
y_size = array.size
x_size = array.size
idx_map = Array.new(n){ [] }
m.times.map { |mm| n.times.map { |nn| idx_map[nn][mm] = [nn + x, mm + y] } }
before = [(idx_map.map(&:shift)).concat(idx_map.pop).concat(idx_map.map(&:pop).reverse).concat(idx_map.shift.reverse)].flatten(1)
after = before.rotate(rotations)
tmp = array.map(&:dup)
before.size.times.map { |idx| array[before[idx][0]][before[idx][1]] = tmp[after[idx][0]][after[idx][1]]}

array.each { |e| p e }

#=> [1, 2, 3, 4, 5, 6]
#=> [7, 8, 9, 10, 11, 12]
#=> [13, 14, 15, 16, 17, 18]
#=> [19, 20, 21, 22, 23, 24]
#=> 
#=> [13, 7, 1, 2, 3, 4]
#=> [19, 8, 9, 10, 11, 5]
#=> [20, 14, 15, 16, 17, 6]
#=> [21, 22, 23, 24, 18, 12]

您还可以旋转从（1,1）开始的3x3子矩阵，例如n = 3，m = 3，x = 1，y = 1和rotations = -1：

#=> [1, 2, 3, 4, 5, 6]
#=> [7, 9, 10, 16, 11, 12]
#=> [13, 8, 15, 22, 17, 18]
#=> [19, 14, 20, 21, 23, 24]

- iGian

如果MxN的矩阵具有不同的M和N，这个程序能正常工作吗？ - Jamy

我设置了 array = (1..24).each_slice(6).to_a（4行，6列），n=4; m=6; x=0; y=0; rotations=2，然后运行了你的代码，从 raise 开始。它在以 before.size.times.map 开头的那一行引发了一个异常 "undefined method '[]' for nil:NilClass"。顺便说一下，我认为最后四行有一个复制粘贴错误，因为你只旋转了一个3x3的数组，却产生了一个4x4的数组！ - Cary Swoveland

@CarySwoveland，我想我把n和m搞反了，请尝试将n设置为6，m设置为4（在我的模型中，n代表列数，m代表行数）。 - iGian

当 n=6，m=4，rotations = 2 且

array(1..24).each_slice(6).to_a #=> [[1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12], [13, 14, 15, 16, 17, 18], [19, 20, 21, 22, 23, 24]]

时，我得到了 [13, 19, 20, 21, 22, 23, 24, 18, 12, 6, 5, 4, 3, 2, 1, 7]（不正确的结果）。你测试过了吗？（我相信我们都在这个问题上花费了比平常更多的时间。） - Cary Swoveland

@CarySwoveland，我想现在已经修复了。请注意，负旋转意味着逆时针方向。 - iGian

0

我觉得将我的代码与 @Humbledore 的进行基准测试会很有趣。(@iGian: 如果你能编辑你的答案，将其包装在一个带有参数 matrix 和 nbr_rotations 的方法中，我可以将你的代码添加到基准测试中)。

def nxt(rows, cols, row, col)
  case row     
  when rows[:first]
    col == cols[:last]  ? [row+1, col] : [row, col+1]
  when rows[:last]
    col == cols[:first] ? [row-1, col] : [row, col-1]
  else
    col == cols[:last]  ? [row+1, col] : [row-1, col]
  end
end

def cary1(matrix, n)
  arr = matrix.dup.map(&:dup)
  nrows, ncols = arr.size, arr.first.size     
  0.upto([nrows, ncols].min/2-1) do |m|
    rows = { first: m, last: nrows-m-1 }
    cols = { first: m, last: ncols-m-1 }
    rect_size = 2 * (nrows + ncols) - 8*m - 4
    rotations = n % rect_size
    row = col = rrow = rcol = m
    rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }
    rect_size.times do
      arr[row][col] = matrix[rrow][rcol]
      row, col   = nxt(rows, cols,  row,  col)
      rrow, rcol = nxt(rows, cols, rrow, rcol)
    end
  end
  arr
end

def first_replacement_loc(rows, cols, rotations)
  ncm1 = cols[:last]-cols[:first]       
  nrm1 = rows[:last]-rows[:first]
  return [rows[:first], cols[:first]+rotations] if rotations <= ncm1
  rotations -= ncm1
  return [rows[:first]+rotations, cols[:last]] if rotations <= nrm1
  rotations -= nrm1
  return [rows[:last], cols[:last]-rotations] if rotations <= ncm1
  rotations -= ncm1
  [rows[:last]-rotations, cols[:first]]
end

def cary2(matrix, n)
  arr = matrix.dup.map(&:dup)
  nrows, ncols = arr.size, arr.first.size     
  0.upto([nrows, ncols].min/2-1) do |m|
    rows = { first: m, last: nrows-m-1 }
    cols = { first: m, last: ncols-m-1 }
    rect_size = 2 * (nrows + ncols) - 8*m - 4
    rotations = n % rect_size
    row = col = m
    rrow, rcol = first_replacement_loc(rows, cols, rotations)
    rect_size.times do
      arr[row][col] = matrix[rrow][rcol]
      row, col   = nxt(rows, cols,  row,  col)
      rrow, rcol = nxt(rows, cols, rrow, rcol)
    end
  end
  arr
end

def humbledore(matrix, rotate)
  rows, cols = matrix.size, matrix.first.size
  layers, str_cols = [rows, cols].min / 2, ""
  # cols.times do str_cols << "%5s " end
  temp_rows = []
  (0...layers).each do |layer|
    row = []
    (layer...rows - 1 - layer).each do |i|
      row << matrix[i][layer]
    end
    (layer...cols - 1 - layer).each do |i|
      row << matrix[rows - 1 - layer][i]
    end
    (rows - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[i][cols - 1 - layer]
    end
    (cols - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[layer][i]
    end
    temp_rows << row
  end
  result = (1..( rows * cols )).each_slice(rows).to_a
  (0...layers).each do |layer|
    row = temp_rows[layer]
    shift = rotate % row.size
    idx = -shift
    (layer...rows - 1 - layer).each do |i|
      result[i][layer] = row[idx]
      idx += 1
      idx %= row.size
    end
    (layer...cols - 1 - layer).each do |i|
      result[rows - 1 - layer][i] = row[idx]
      idx += 1
      idx %= row.size
    end
    (rows - 1 - layer).step(layer + 1, -1).each do |i|
      result[i][cols - 1 - layer] = row[idx]
      idx += 1
      idx %= row.size
    end
    (cols - 1 - layer).step(layer + 1, -1).each do |i|
      result[layer][i] = row[idx]
      idx += 1
      idx %= row.size
    end
  end
  result
end

require 'benchmark'

def test(rows, cols, rotations)
  puts "\nrows = #{rows}, cols = #{cols}, rotations = #{rotations}"
  matrix = (1..rows*cols).each_slice(cols).to_a
  Benchmark.bm do |x|
    x.report("Cary1") { cary1(matrix, rotations) }
    x.report("Cary2") { cary2(matrix, rotations) }
    x.report("Humbledore") { humbledore(matrix, rotations) }
  end
end

test 10,10,1
rows = 10, cols = 10, rotations = 1
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.000077)
   Cary2       0.000000   0.000000   0.000000 (  0.000074)
   Humbledore  0.000000   0.000000   0.000000 (  0.000051)

test 10,10,78
rows = 10, cols = 10, rotations = 78
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.000079)
   Cary2       0.000000   0.000000   0.000000 (  0.000061)
   Humbledore  0.000000   0.000000   0.000000 (  0.000053)

test 100,100,378
rows = 100, cols = 100, rotations = 378
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.007673)
   Cary2       0.015625   0.000000   0.015625 (  0.005168)
   Humbledore  0.000000   0.000000   0.000000 (  0.002919)

test 500,500,1950
rows = 500, cols = 500, rotations = 1950
   user         system      total        real
   Cary1       0.171875   0.000000   0.171875 (  0.166671)
   Cary2       0.140625   0.000000   0.140625 (  0.137141)
   Humbledore  0.046875   0.000000   0.046875 (  0.053705)

test 500,1000,2950
rows = 500, cols = 1000, rotations = 2950
   user         system      total        real
   Cary1       0.296875   0.000000   0.296875 (  0.292997)
   Cary2       0.234375   0.000000   0.234375 (  0.248384)
   Humbledore  0.125000   0.000000   0.125000 (  0.103964)

基准测试报告以秒为单位显示执行时间。结果非常一致。

请注意，在我进行的所有测试中，数组的列数至少与行数相同。这是因为在 Humbledore 的代码中，每当行数超过列数时，都会引发 NoMethodError (undefined method '[]=' for nil:NilClass) 异常。(例如尝试使用 test 3,2,1。) 错误消息出现在以下代码块的第二行。

(layer...cols - 1 - layer).each do |i|
  result[rows - 1 - layer][i] = row[idx]
  idx += 1
  idx %= row.size
end

我认为问题很容易修复。

- Cary Swoveland

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cary Swoveland · Accepted Answer

代码

def nxt(rows, cols, row, col)
  case row     
  when rows[:first]
    col == cols[:last]  ? [row+1, col] : [row, col+1]
  when rows[:last]
    col == cols[:first] ? [row-1, col] : [row, col-1]
  else
    col == cols[:last]  ? [row+1, col] : [row-1, col]
  end
end

def rotate_array_times(matrix, n)
  arr = matrix.dup.map(&:dup)
  nrows, ncols = arr.size, arr.first.size     
  0.upto([nrows, ncols].min/2-1) do |m|
    rows = { first: m, last: nrows-m-1 }
    cols = { first: m, last: ncols-m-1 }
    rect_size = 2 * (nrows + ncols) - 8*m - 4
    rotations = n % rect_size
    row = col = rrow = rcol = m
    rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }
    rect_size.times do
      arr[row][col] = matrix[rrow][rcol]
      row, col   = nxt(rows, cols,  row,  col)
      rrow, rcol = nxt(rows, cols, rrow, rcol)
    end
  end
  arr
end

例子

matrix = [ 
  [ 1,  2,  3,  4],
  [ 5,  6,  7,  8],
  [ 9, 10, 11, 12],
  [13, 14, 15, 16]
]

(1..3).each { |n| p rotate_array_times(matrix, n) }
  [[2,  3,  4,  8],
   [1,  7, 11, 12],
   [5,  6, 10, 16],
   [9, 13, 14, 15]]

  [[3,  4,  8, 12],
   [2, 11, 10, 16],
   [1,  7,  6, 15],
   [5,  9, 13, 14]]

  [[4,  8, 12, 16],
   [3, 10,  6, 15],
   [2, 11,  7, 14],
   [1,  5,  9, 13]]

matrix = (1..24).each_slice(4).to_a
  #=> [[ 1,  2,  3,  4],
  #    [ 5,  6,  7,  8],
  #    [ 9, 10, 11, 12],
  #    [13, 14, 15, 16],
  #    [17, 18, 19, 20],
  #    [21, 22, 23, 24]]
(1..3).each { |n| p rotate_array_times(matrix, n) }
  #=> [[ 2,  3,  4,  8],
  #    [ 1,  7, 11, 12],
  #    [ 5,  6, 15, 16],
  #    [ 9, 10, 19, 20],
  #    [13, 14, 18, 24],
  #    [17, 21, 22, 23]]

  #   [[ 3,  4,  8, 12],
  #    [ 2, 11, 15, 16],
  #    [ 1,  7, 19, 20],
  #    [ 5,  6, 18, 24],
  #    [ 9, 10, 14, 23],
  #    [13, 17, 21, 22]]

  #   [[ 4,  8, 12, 16],
  #    [ 3, 15, 19, 20],
  #    [ 2, 11, 18, 24],
  #    [ 1,  7, 14, 23],
  #    [ 5,  6, 10, 22],
  #    [ 9, 13, 17, 21]]

matrix = (1..48).each_slice(8).to_a
  #=> [[ 1,  2,  3,  4,  5,  6,  7,  8],
  #    [ 9, 10, 11, 12, 13, 14, 15, 16],
  #    [17, 18, 19, 20, 21, 22, 23, 24],
  #    [25, 26, 27, 28, 29, 30, 31, 32],
  #    [33, 34, 35, 36, 37, 38, 39, 40],
  #    [41, 42, 43, 44, 45, 46, 47, 48]]

(1..3).each { |n| p rotate_array_times(matrix, n) }
[[ 2,  3,  4,  5,  6,  7,  8, 16],
 [ 1, 11, 12, 13, 14, 15, 23, 24],
 [ 9, 10, 20, 21, 22, 30, 31, 32],
 [17, 18, 19, 27, 28, 29, 39, 40],
 [25, 26, 34, 35, 36, 37, 38, 48],
 [33, 41, 42, 43, 44, 45, 46, 47]]

[[ 3,  4,  5,  6,  7,  8, 16, 24], 
 [ 2, 12, 13, 14, 15, 23, 31, 32],
 [ 1, 11, 21, 22, 30, 29, 39, 40],
 [ 9, 10, 20, 19, 27, 28, 38, 48],
 [17, 18, 26, 34, 35, 36, 37, 47], 
 [25, 33, 41, 42, 43, 44, 45, 46]]

[[ 4,  5,  6,  7,  8, 16, 24, 32],
 [ 3, 13, 14, 15, 23, 31, 39, 40],
 [ 2, 12, 22, 30, 29, 28, 38, 48],
 [ 1, 11, 21, 20, 19, 27, 37, 47],
 [ 9, 10, 18, 26, 34, 35, 36, 46],
 [17, 25, 33, 41, 42, 43, 44, 45]]

说明

nxt

nxt(rows, cols, row, col)给定行和列的索引row和col，返回替换索引[row,col]处的元素（也在周长上）的“下一个”元素的索引[next_row,next_col]。该子阵列由散列rows和cols给出，每个散列都具有键:first和:last。

我们考虑一个具有4个元素（行）的数组arr，每个元素（行）具有6个值（列）。那么

nrows, ncols = arr.size, arr.first.size
  #=> [4, 6]

如果 m = 0。

rows = { first: m, last: nrows-m-1 }
  #=> {:first=>0, :last=>3}
cols = { first: m, last: ncols-m-1 }
  #=> {:first=>0, :last=>5}

可以看出，rows和cols描述了数组matrix的“外围”。我们可以看到nxt的工作原理如下。

first_row, first_col = rows[:first], cols[:first]
row, col = first_row, first_col
print "[#{row}, #{col}]"
loop do
  next_row, next_col = nxt(rows, cols, row, col)
  print "->[#{next_row}, #{next_col}]"
  row, col = next_row, next_col
  (puts; break) if [row, col] == [first_row, first_col]
end
[0, 0]->[0, 1]->[0, 2]->[0, 3]->[0, 4]->[0, 5]->[1, 5]->[2, 5]->[3, 5]->
[3, 4]->[3, 3]->[3, 2]->[3, 1]->[3, 0]->[2, 0]->[1, 0]->[0, 0]

如果 m = 1，上述计算结果为：

[1, 1]->[1, 2]->[1, 3]->[1, 4]->[2, 4]->[2, 3]->[2, 2]->[2, 1]->[1, 1]

rotate_array_times

这个方法是将 matrix 和 arr 的元素按指定方式旋转 n 次并返回结果数组的深层拷贝。

为了加快计算速度，n 被替换为自身的模数。例如对于一个 4x4 的数组，在经过12次迭代后，数组周长将回到其原始值。因此，执行 n % 12 次旋转就足够了。

matrix 包含 n = [matrix.size, matrix.first.size].min 个子数组，它们的周长要进行旋转。每个子数组的左上角坐标为 [m,m]，其中 m = 0..n-1。

对于由 m 指定的子数组，第一步是确定 matrix 中要替换 arr 中 [m,m] 元素的位置。这在下面的代码行中完成：

rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }

(""rrow"和"rcol"分别代表“替换行”和“替换列”。此时，位于arr位置row #=> m，col #=> m的元素将被替换为matrix中由rrow和rcol给出位置的元素。然后，对于需要旋转的子数组周长中的每个元素，执行以下操作：)

arr[row][col] = matrix[rrow][rcol]
row, col   = nxt(rows, cols,  row,  col)
rrow, rcol = nxt(rows, cols, rrow, rcol)

优化效率

通过替换以下这行代码，可以稍微提高效率：

rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }

使用

rrow, rcol = first_replacement_loc(rows, cols, rotations)

并添加以下方法。

def first_replacement_loc(rows, cols, rotations)
  ncm1 = cols[:last]-cols[:first]       
  nrm1 = rows[:last]-rows[:first]
  return [rows[:first], cols[:first]+rotations] if rotations <= ncm1
  rotations -= ncm1
  return [rows[:first]+rotations, cols[:last]] if rotations <= nrm1
  rotations -= nrm1
  return [rows[:last], cols[:last]-rotations] if rotations <= ncm1
  rotations -= ncm1
  [rows[:last]-rotations, cols[:first]]
end