[n*m]螺旋矩阵的sql实现
原帖链接: http://www.itpub.net/514589.html
[@more@]
在itpub不知不觉也快两年了, 回帖也已数百.
不知不觉间看贴回帖已成了一种习惯, 今日开启自己blog, 希望能结交更多的朋友.
思索数日, 不只从何开始, 索性就以一篇置顶帖中的回帖作为开篇.
原帖链接: http://www.itpub.net/514589.html
题目描述:
如下是一个4*4的矩阵:
1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7
按照上面矩阵的规律, 请用PL/SQL写出当M*N时的矩阵算法
个人回帖见20楼(虽其后也有回帖, 但是主算法在这里已固定)
SQL> -- 逆时针的
SQL> select --i,
2 sum(decode(j, 1, rn)) as co11,
3 sum(decode(j, 2, rn)) as co12,
4 sum(decode(j, 3, rn)) as co13,
5 sum(decode(j, 4, rn)) as co14
6 from (select i, j, rank() over(order by tag) as rn
7 from (select i,
8 j,
9 -- 逆时针螺旋特征码 counter-clockwise
10 case least(j - 1, 4 - i, 4 - j, i - 1)
11 when j - 1 then
12 (j - 1) || '1' || i
13 when 4 - i then
14 (4 - i) || '2' || j
15 when 4 - j then
16 (4 - j) || '3' || (4 - i)
17 when i - 1 then
18 (i - 1) || '4' || (4 - j)
19 end as tag
20 from (select level as i from dual connect by level <= 4) a,
21 (select level as j from dual connect by level <= 4) b))
22 group by i
23 /
CO11 CO12 CO13 CO14
---------- ---------- ---------- ----------
1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7
SQL> -- 顺时针的
SQL> select --i,
2 sum(decode(j, 1, rn)) as co11,
3 sum(decode(j, 2, rn)) as co12,
4 sum(decode(j, 3, rn)) as co13,
5 sum(decode(j, 4, rn)) as co14
6 from (select i, j, rank() over(order by tag) as rn
7 from (select i,
8 j,
9 -- 顺时针螺旋特征码 clockwise
10 case least(i - 1, 4 - j, 4 - i, j - 1)
11 when i - 1 then
12 (i - 1) || '1' || j
13 when 4 - j then
14 (4 - j) || '2' || i
15 when 4 - i then
16 (4 - i) || '3' || (4 - j)
17 when j - 1 then
18 (j - 1) || '4' || (4 - i)
19 end as tag
20 from (select level as i from dual connect by level <= 4) a,
21 (select level as j from dual connect by level <= 4) b))
22 group by i
23 /
CO11 CO12 CO13 CO14
---------- ---------- ---------- ----------
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
----------
解法中个人提出了"螺旋特征码", 这里就此给出解释
(虽然在27楼给出了其解释, 可是还有朋友回复说不明白, 因个人语文水平有限, 没有继续解释, 惭愧啊, 在这里再次重新解释, 希望朋友们可以明白.)
为了便于说明, 用原题中的逆时针螺旋矩阵为例.
1 12 - 11 -10
| | |
2 13 16 9
| | + | |
3 14 - 15 8
| |
4 - 5 - 6 - 7
在矩阵图中用 '|' 和 '-' 来标识出螺旋的方式, 显然螺旋的起点在(1,1), 终点在(2,3) ( (row, col) ).
从螺旋的自身特定, 它是从外向内的, 虚拟一个螺旋的中点, 如上图就是 "+" 所在的位置, 显然对于不同层上的点, 靠外的比靠内的从顺序上来说优先
对于在同一层上的点, 就螺旋的逆时针旋转来说, 会按照 "左 -> 下 -> 右 -> 上" 的顺序来决定点的优先级,
对于同一层同一侧的点来说, 距离前一侧越近优先级越高, 如最外层左侧的四个点, 前一侧为上侧, 距离最近的1比距离稍远的2优先级高
由以上两点可以得出这个螺旋上16个点的优先级判断的规则, 可是如何把它变成可识别的呢?
由此, 我提出了"螺旋特征码", 如果可以把这种特征用便于排序的码不就可以清楚的表示螺旋上每个点了吗.
特征码由三个部分组成:
第一部分: 表示点所在层
第二部分: 表示点所在侧
第三部分: 表示点距离前一侧的距离
如果把三个部分能够用便于排序的字符串表示出来, 那么特征码自然就产生了
特征码的三个部分取值:
第一部分: 表示点所在层,
如上图, 显然 第一列+最后一行+最后一列+第一行组成了最外层,
转义成代码(i表示行, j表示列): 第一列就是 j-1, 最后一行就是 4-i, 最后一列就是4-i, 第一行就是i-1;
为什么会是这样定值呢?
因为这样可以保证, 当不同侧的点处于同一层时, 层值相同即 j-1 = 4-i = 4-i = i-1
第二部分: 表示点所在侧
如前所述 "左 -> 下 -> 右 -> 上"四个侧应该是有顺序的, 为便于表示, 分别用 1, 2, 3, 4 代表.
第三部分: 表示点距离前一侧的距离
距离下一侧的距离, 这个是一个相对值, 因此在我的实现示例中没有使用统一的标准, 这里给出一个统一的距离计算标准就是
位于左侧的点, 距离前一侧(即上侧)的距离是 i-1,
位于下侧的点, 距离前一侧(即左侧)的距离是 j-1,
位于右侧的点, 距离前一侧(即下侧)的距离是 4-i,
位于上侧的点, 距离前一侧(即右侧)的距离是 4-j.
由此, 把特征码的三个部分按照先后顺序, 链接成字符串, 形成单一的"螺旋特征码".
相对应"螺旋特征码"的生成代码如下:
-- 逆时针螺旋特征码 counter-clockwise ([4*4]逆时针螺旋矩阵特征码)
case least(j - 1, 4 - i, 4 - j, i - 1)
when j - 1 then -- 左侧
(j - 1) || '1' || (i - 1)
when 4 - i then -- 下侧
(4 - i) || '2' || (j - 1)
when 4 - j then -- 右侧
(4 - j) || '3' || (4 - i)
when i - 1 then -- 上侧
(i - 1) || '4' || (4 - j)
end as tag
特征码在排序比较的时候必须遵循先比较第一部分, 再比较第二部分, 最后比较第三部分,
因此特征码每部分的长度必须是相同的, 而根据矩阵的对称性可以看出,
上面这段[4*4]逆时针螺旋矩阵特征码的扩展性是[19*19], 如果出现20, 特征码的顺序就会错误.
下面一段代码是一个[n*m]顺时针螺旋矩阵的生成代码, 其中的含义在对上面简单示例的理解基础上去理解吧
var n number;
var m number;
exec :n := &n; :m=&m;
with t as (
select :n as n, :m as m from dual
)
select replace(max(sys_connect_by_path(rank, ',')), ',') str
from (select i, j, to_char(rank() over(order by tag), '999999') as rank
from (select i,
j,
-- 顺时针螺旋特征码 clockwise
case least(i - 1, m - j, n - i, j - 1)
when i - 1 then
to_char(i - 1, 'fm0000') || '1' ||
to_char(j - 1, 'fm0000')
when m - j then
to_char(m - j, 'fm0000') || '2' ||
to_char(i - 1, 'fm0000')
when n - i then
to_char(n - i, 'fm0000') || '3' ||
to_char(m - j, 'fm0000')
when j - 1 then
to_char(j - 1, 'fm0000') || '4' ||
to_char(n - i, 'fm0000')
end as tag
from (select n, level as i from t connect by level <= n) a,
(select m, level as j from t connect by level <= m) b))
start with j = 1
connect by j - 1 = prior j and i = prior i
group by i
/
-------------
ps:
1. 原帖中也有很多朋友的回复值得看值得学习, 如 zuochc 在此基础上做了对矩阵90度旋转的实现;
2. 实现方法中使用了connect by语句来构造数据, 适用与oracle 9.2 或更高版本, 如果版本低, 需要通过其他方式来实现,
以后会在blog中专门写构造数据的文章;
3. 在实现方法中还用到了行列转换([n*m]行转为n行m列的转换)和用sys_connect_by_path多行数据合并为一行的方法,
以后也会在blog中单独写.
4. 最后谢谢大家来看我的blog, ^_^