ruby - 将 Matrix 逆时针旋转 n 个位置
ruby - rotate Matrix anti-clockwise by n position
给定一个二维矩阵：
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 & 的重复问题，因为我想要实现的是逆时针旋转值。
我目前的实施和问题
我当前的实现仅以逆时针方式打印出值，但不会旋转值。
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、4,4、4x8 等..
没有"empty squares"。
代码
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
给定行和列索引 row 和 col，nxt(rows, cols, row, col) returns 周界上 "next" 元素的索引 [next_row, next_col]一个子数组的子数组，该子数组将在一次迭代中替换索引 [row, 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的"perimeter"。我们可以看到 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、arrr的深层副本，其元素按规定的次数旋转n次，然后returns得到结果数组。
为了加快计算速度，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" 分别代表 "replacement row" 和 "replacement col"。此时row #=> m、col #=> m位置的arr元素要替换rrow和[=61]位置的matrix元素=].然后执行以下操作，次数与子数组周边要旋转的元素数一样多：
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
这是另一种实现（我没有做方法，只是需要改进的逻辑）。
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]
TL:DR
如果您想直接跳到解决方案代码，请跳到该答案的底部。
说明
你需要分解问题并独立解决每一个问题。
问题
- 获取层数
- 以反向螺旋形式循环以获得预期值
- 根据给定的旋转参数移动它们
让我们分别过一遍每个点：
获取层数
您需要一种获取层数的方法。下面的矩阵有 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次：最外层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
)
我认为将我的代码与@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)
Benchmark 以秒为单位报告执行时间。结果发现还是比较一致的。
请注意，在我执行的所有测试中，数组的列数至少与行数一样大。这是因为每当行数超过列数时，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
我希望这个问题很容易解决。
给定一个二维矩阵：
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 &
我目前的实施和问题
我当前的实现仅以逆时针方式打印出值，但不会旋转值。
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、4,4、4x8 等..
没有"empty squares"。
代码
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
给定行和列索引 row 和 col，nxt(rows, cols, row, col) returns 周界上 "next" 元素的索引 [next_row, next_col]一个子数组的子数组，该子数组将在一次迭代中替换索引 [row, 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的"perimeter"。我们可以看到 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、arrr的深层副本，其元素按规定的次数旋转n次，然后returns得到结果数组。
为了加快计算速度，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" 分别代表 "replacement row" 和 "replacement col"。此时row #=> m、col #=> m位置的arr元素要替换rrow和[=61]位置的matrix元素=].然后执行以下操作，次数与子数组周边要旋转的元素数一样多：
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
这是另一种实现（我没有做方法，只是需要改进的逻辑）。
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]
TL:DR
如果您想直接跳到解决方案代码，请跳到该答案的底部。
说明
你需要分解问题并独立解决每一个问题。
问题
- 获取层数
- 以反向螺旋形式循环以获得预期值
- 根据给定的旋转参数移动它们
让我们分别过一遍每个点：
获取层数
您需要一种获取层数的方法。下面的矩阵有 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次：最外层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
)
我认为将我的代码与@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)
Benchmark 以秒为单位报告执行时间。结果发现还是比较一致的。
请注意，在我执行的所有测试中，数组的列数至少与行数一样大。这是因为每当行数超过列数时，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
我希望这个问题很容易解决。