算法问题:用SQL写出当M*N时的螺旋矩阵算法
以下是一个4*4的矩阵:
1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7
请照上面矩阵的规律, 用SQL写出当M*N时的矩阵算法。
实现的sql与效果:
代码:---------------------------------------------
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
---------------------------------------------------------
以上两种旋转都是由外向内的, 如果有兴趣也可以做成由内向外的。
不过如果大家还要把结果90度旋转, 在顺序固定的情况下, 应该就是行列转换的问题了。
不过如果要做成圆形的, 我觉得不太可能了, 正n边形倒是可以考虑, 不过要看n的值是多大, 如果趋于正无穷, 那就是圆了, 下面我们来具体说一下这个螺旋特征码的算法原理。
螺旋总要有个起点, 就用上面的那个结果来说明吧，起点是(1,1), 如果是顺时针的话, 旋转时依次走过的途径是 上->右->下->左->上->右->下->左..., 知道最后在螺旋中心结束, 但是可以注意到旋转是会越来越远离外边界
根据这个我们就可以获取螺旋特征码了
4*4的矩阵, 那么可以认为 i=1, j=1, i=4, j=4, 这就是这个螺旋的4个边界, 顺时针旋转时, 离边界越近, 那么顺序就越靠前, 当距离边界相同时, 边界的优先级就要根据 上右下左(起点为1,1, 顺时针旋转的边界优先级) 而定了, 如果这个也相同, 那么就要根据这个点离前一个边界的距离而定, 离的越近, 优先级越高, 根据以上规则, 可以得出特征码共有三位, 第一位代表距离边界的距离, 第二位代表距离哪个边界最近(我的sql中用1,2,3,4分别表示四个边界), 第三位代表距离前一个边界的距离(因为目的是为了排序, 计算时没有严格按照这个距离值进行表示^_^)
对应上面螺旋特征码的规则, 使用case least(...)判断离边界的距离和距离最近的边界是那个边界, when ... then后的取值再确定距离前一个边界的距离, 这样就完成了特征码, 剩下的就是对特征码排序和行列转换了。
现在现换一下思路, 用SYS_CONNECT_BY_PATH函数, 实现N的矩阵生成:
代码:------------------------------------------------
SQL> var n number;
SQL> exec :n := 3;
PL/SQL 过程已成功完成。
SQL> select replace(max(sys_connect_by_path(rank, ',')), ',') str
2 from (select i, j,
3 to_char(rank() over(order by tag), '9999') as rank
4 from (select i,
5 j,
6 -- 逆时针螺旋特征码 counter-clockwise
7 case least(j - 1, :n - i, :n - j, i - 1)
8 when j - 1 then
9 (j - 1) || '1' || i
10 when :n - i then
11 (:n - i) || '2' || j
12 when :n - j then
13 (:n - j) || '3' || (:n - i)
14 when i - 1 then
15 (i - 1) || '4' || (:n - j)
16 end as tag
17 from (select level as i from dual connect by level <= :n) a,
18 (select level as j from dual connect by level <= :n) b
19 )
20 )
21 start with j = 1
22 connect by j - 1 = prior j and i = prior i
23 group by i
24 order by i;
STR
---------------------------------------------------------
1 8 7
2 9 6
3 4 5
SQL> exec :n := 4;
PL/SQL 过程已成功完成。
SQL> /
STR
-----------------------------------------------------
1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7
SQL> exec :n := 5;
PL/SQL 过程已成功完成。
SQL> /
STR
------------------------------------------------------
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
SQL>
我们可以尝试填足一下:
代码:--------------------------------------------------
SQL> exec :n := 5
PL/SQL 过程已成功完成。
SQL> select replace(max(sys_connect_by_path(rank, ',')), ',') str
2 from (select i, j,
3 case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then ' '
4 else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank,
5 min(j) over(partition by i) minj
6 from (select i,
7 j,
8 -- 顺时针螺旋特征码 counter-clockwise
9 case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1)
10 when i - j then
11 :n - (i - j) || '1' || i
12 when i + j - :n - 1 then
13 :n - (i + j - :n - 1) || '2' || j
14 when j - i then
15 :n - (j - i) || '3' || (:n - i)
16 when :n - i - j + 1 then
17 :n - (:n - i - j + 1) || '4' || i
18 end as tag
19 from (select level as i from dual connect by level <= :n) a,
20 (select level as j from dual connect by level <= :n) b
21 -- where abs(i - j) < floor(:n / 2 + .6)
22 -- and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n
23 )
24 )
25 start with j = minj
26 connect by j - 1 = prior j and i = prior i
27 group by i
28 order by i;
STR
-----------------------------------------------------------
7
8 12 6
1 9 13 11 5
2 10 4
3
SQL> exec :n := 7;
PL/SQL 过程已成功完成。
SQL> /
STR
-----------------------------------------------------------
10
11 19 9
12 20 24 18 8
1 13 21 25 23 17 7
2 14 22 16 6
3 15 5
4
已选择7行。
SQL> exec :n := 9;
PL/SQL 过程已成功完成。
SQL> /
STR
---------------------------------------------------------------
13
14 26 12
15 27 35 25 11
16 28 36 40 34 24 10
1 17 29 37 41 39 33 23 9
2 18 30 38 32 22 8
3 19 31 21 7
4 20 6
5
已选择9行。
SQL> exec :n := 8
PL/SQL 过程已成功完成。
SQL> /
STR
------------------------------------------------------
5 4
6 18 17 3
7 19 27 26 16 2
8 20 28 32 31 25 15 1
9 21 29 30 24 14
10 22 23 13
11 12
对于比较大的N值, 需对"顺时针螺旋特征码"的组成进行适当修改:
代码:----------------------------------------------------
1 select replace(max(sys_connect_by_path(rank, ',')), ',') str
2 from (select i, j,
3 case when rank() over(order by tag) - floor(:n * :n / 2) <= 0 then ' '
4 else to_char(rank() over(order by tag) - floor(:n * :n / 2), '9999') end as rank,
5 min(j) over(partition by i) minj
6 from (select i,
7 j,
8 -- 逆时针螺旋特征码 counter-clockwise
9 case greatest(i - j, i + j - :n - 1, j - i, :n - i - j + 1)
10 when i - j then
11 chr(:n - (i - j)) || '1' || chr(i)
12 when i + j - :n - 1 then
13 chr(:n - (i + j - :n - 1)) || '2' || chr(j)
14 when j - i then
15 chr(:n - (j - i)) || '3' || chr((:n - i))
16 when :n - i - j + 1 then
17 chr(:n - (:n - i - j + 1)) || '4' || chr(i)
18 end as tag
19 from (select level as i from dual connect by level <= :n) a,
20 (select level as j from dual connect by level <= :n) b
21 -- where abs(i - j) < floor(:n / 2 + .6)
22 -- and i + j between floor(:n / 2 + .6) + 1 and floor(:n / 2 + .6) + :n
23 )
24 )
25 start with j = minj
26 connect by j - 1 = prior j and i = prior i
27 group by i
28* order by i
SQL> /
STR
-----------------------------------------------------
19
20 40 18
21 41 57 39 17
22 42 58 70 56 38 16
23 43 59 71 79 69 55 37 15
24 44 60 72 80 84 78 68 54 36 14
1 25 45 61 73 81 85 83 77 67 53 35 13
2 26 46 62 74 82 76 66 52 34 12
3 27 47 63 75 65 51 33 11
4 28 48 64 50 32 10
5 29 49 31 9
6 30 8
7
-------------------------------------------------------
想来是的, 这样你看如何?
代码:--------------------------------------------------
1 select replace(max(sys_connect_by_path(rank, ',')), ',') str
2 from (select i, j,
3 to_char(rank() over(order by tag), '9999') as rank
4 from (select i,
5 j,
6 -- 逆时针螺旋特征码 counter-clockwise
7 case least(j - 1, &&1 - i, &1 - j, i - 1)
8 when j - 1 then
9 (j - 1) || '1' || i
10 when &1 - i then
11 (&1 - i) || '2' || j
12 when &1 - j then
13 (&1 - j) || '3' || (&1 - i)
14 when i - 1 then
15 (i - 1) || '4' || (&1 - j)
16 end as tag
17 from (select level as i from dual connect by level <= &1) a,
18 (select level as j from dual connect by level <= &1) b
19 )
20 )
21 start with j = 1
22 connect by j - 1 = prior j and i = prior i
23 group by i
24* order by i
SQL> /
输入 1 的值: 5
原值 7: case least(j - 1, &&1 - i, &1 - j, i - 1)
新值 7: case least(j - 1, 5 - i, 5 - j, i - 1)
原值 10: when &1 - i then
新值 10: when 5 - i then
原值 11: (&1 - i) || '2' || j
新值 11: (5 - i) || '2' || j
原值 12: when &1 - j then
新值 12: when 5 - j then
原值 13: (&1 - j) || '3' || (&1 - i)
新值 13: (5 - j) || '3' || (5 - i)
原值 15: (i - 1) || '4' || (&1 - j)
新值 15: (i - 1) || '4' || (5 - j)
原值 17: from (select level as i from dual connect by level <= &1) a,
新值 17: from (select level as i from dual connect by level <= 5) a,
原值 18: (select level as j from dual connect by level <= &1) b
新值 18: (select level as j from dual connect by level <= 5) b
STR
-----------------------------------------------------
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
SQL>--------------------------------------------------
使用前, 给声明m和n并赋值
代码:-------------------------------------------------
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
