发现一位专门用SQL解各种谜题的高人！

newkid

很简单的一个字符串拆分的SQL:

WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT LEVEL,SUBSTR(str,level,1)
  FROM data
CONNECT BY str = PRIOR str
            AND LEVEL<=LENGTH(str);

ERROR:
ORA-01436: CONNECT BY loop in user data

这里出现了死循环，因为没有指明前后级的关系，str = PRIOR str会取到自身。

加上NOCYCLE:
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT LEVEL,SUBSTR(str,level,1)
  FROM data
CONNECT BY NOCYCLE str = PRIOR str
            AND LEVEL<=LENGTH(str);

     LEVEL S
---------- -
         1 1
         1 5

虽然可以运行但结果是错的，因为ORACLE检测到循环后就拒绝继续。


我的办法是：
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT rn,SUBSTR(str,rn,1)
  FROM data, (SELECT ROWNUM rn FROM (SELECT MAX(LENGTH(str)) len FROM data) CONNECT BY ROWNUM<=len)
WHERE rn<=LENGTH(str);

        RN S
---------- -
         1 1
         1 5
         2 2
         2 6
         3 3
         4 4

6 rows selected.

Frank zhou 的办法：
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT LEVEL,SUBSTR(str,level,1)
  FROM data
CONNECT BY str = PRIOR str
            AND LEVEL<=LENGTH(str)
            AND PRIOR DBMS_RANDOM.VALUE IS NOT NULL;

     LEVEL S
---------- -
         1 1
         2 2
         3 3
         4 4
         1 5
         2 6

这里 DBMS_RANDOM.VALUE 消除了循环，因为上一轮的随机值和这一轮是不相同的，因为ORACLE认为循环没有出现，所以递归得以继续，一直到LEVEL超出长度为止。
这个 PRIOR DBMS_RANDOM.VALUE IS NOT NULL 就相当于：
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT LEVEL,SUBSTR(str,level,1)
  FROM data
CONNECT BY str = PRIOR str
            AND LEVEL<=LENGTH(str)
            AND PRIOR DBMS_RANDOM.VALUE <>DBMS_RANDOM.VALUE;

如果每一轮的随机值碰巧出现了一样的，那么ORACLE一样会拒绝：
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
SELECT LEVEL,SUBSTR(str,level,1)
  FROM data
CONNECT BY str = PRIOR str
            AND LEVEL<=LENGTH(str)
            AND PRIOR DBMS_RANDOM.VALUE(1,1) IS NOT NULL;

ERROR:
ORA-01436: CONNECT BY loop in user data

我故意用了DBMS_RANDOM.VALUE(1,1), 结果循环又出现了。

如果用11GR2的递归WITH就没有这些问题：
WITH DATA AS (
  SELECT '1234' AS str FROM DUAL
  UNION ALL SELECT '56' FROM DUAL
  )
,t(lvl,c,str) AS (
SELECT 1,SUBSTR(str,1,1),str FROM data
UNION ALL
SELECT lvl+1,SUBSTR(str,lvl+1,1),str
  FROM t
WHERE lvl+1<=LENGTH(str)
)
SELECT * FROM t ORDER BY str,lvl;

       LVL C STR
---------- - ----
         1 1 1234
         2 2 1234
         3 3 1234
         4 4 1234
         1 5 56
         2 6 56

yellowlee

快来看牛魔王

newkid

http://oraqa.com/2007/06/24/how- ... in-a-sql-statement/

The following SQL pattern can be used to find matched rows between 2 tables based on required matching criteria in a SQL statement.

把两张表的数据一一配对，条件是t2_compare BETWEEN t1_compare-2 AND t1_compare+2, 并且每一行最多能和一行匹配。
要求匹配对数最多的配对方式。

Here are the requirements.

1) matching rows in t1 to t2
(t2_compare BETWEEN t1_compare-2 AND t1_compare+2 )
2) match to a t2 row at most once, once a row is matched, it can't be used again.
3) The goal is to match as many pairs as possible

create table t1 ( pk integer primary key, t1_compare integer, t1_data  varchar2(10));
create table t2 ( pk integer primary key, t2_compare integer, t2_data varchar2(10));
insert into t1 values ( 1, 10, 'T1 ROW1' );
insert into t1 values ( 2, 12, 'T1 ROW2' );
insert into t1 values ( 3, 14, 'T1 ROW3' );
insert into t1 values ( 4, 16, 'T1 ROW4' );
insert into t1 values ( 5, 18, 'T1 ROW5' );
insert into t1 values ( 6, 19, 'T1 ROW6' );
insert into t1 values ( 7, 128, 'T1 ROW8');
insert into t2 values ( 1, 11, 'T2 ROW1' );
insert into t2 values ( 2, 12, 'T2 ROW2' );
insert into t2 values ( 3, 14, 'T2 ROW3' );
insert into t2 values ( 4, 15, 'T2 ROW4' );
insert into t2 values ( 5, 19, 'T2 ROW5' );
insert into t2 values ( 6, 19, 'T2 ROW6' );
insert into t2 values ( 8, 28, 'T2 ROW18');
insert into t2 values ( 9, 68, 'T2 ROW28');

SQL> select * from t1;

        PK T1_COMPARE T1_DATA
---------- ---------- ----------
         1         10 T1 ROW1
         2         12 T1 ROW2
         3         14 T1 ROW3
         4         16 T1 ROW4
         5         18 T1 ROW5
         6         19 T1 ROW6
         7        128 T1 ROW8                                                  

7 rows selected.

SQL> select * from t2;

        PK T2_COMPARE T2_DATA
---------- ---------- ----------
         1         11 T2 ROW1
         2         12 T2 ROW2
         3         14 T2 ROW3
         4         15 T2 ROW4
         5         19 T2 ROW5
         6         19 T2 ROW6
         8         28 T2 ROW18
         9         68 T2 ROW28                                                

8 rows selected.

SQL> COLUMN t2_pk FORMAT   A8
SQL> COLUMN unmatched_t2 FORMAT A8
SQL> COLUMN STATUS FORMAT  A10

SELECT t1_pk, match as t2_pk, tmp_str as unmatched_t2,
       CASE WHEN t1_pk IS NULL
     THEN 'NO T1'
     WHEN match IS NULL
     THEN 'NO T2'
     ELSE 'MATCHED'
       END AS STATUS
FROM
(SELECT t1.pk t1_pk, row_number() OVER (ORDER BY t1.pk) position,
        ltrim(regexp_replace(XMLAgg(XMLElement(x,t2.pk)
        order by t2.pk),'<X>|</X><X>|</X>',','),',') str,
        CASE WHEN count(t2.pk) != 0 AND t1.pk IS NOT NULL
             THEN count(t2.pk)
      ELSE NULL
        END ct ,
        count(t1.pk) OVER ( ) counter
  FROM t1 FULL OUTER JOIN t2
       ON ( t2_compare BETWEEN t1_compare-2 AND t1_compare+2 )
GROUP BY t1.pk
)
MODEL
DIMENSION BY (position)
MEASURES (t1_pk, str, ct, str as tmp_str, CAST(NULL AS NUMBER) min_tmp,
          counter, ct ct_tmp, CAST(NULL AS VARCHAR2(4000)) match,
          CAST(NULL AS NUMBER) dup, CAST(NULL AS NUMBER) min_dup,
          CAST(NULL AS VARCHAR2(4000)) tmp_ch ,
          CAST(NULL AS VARCHAR2(4000)) tmp_cp
  )
RULES
ITERATE (1000000) UNTIL (ITERATION_NUMBER>= counter[1])
(
min_tmp[ANY] = min(ct_tmp)[ANY],
dup[ANY] = CASE WHEN ct_tmp[CV()] = min_tmp[1]
                 THEN t1_pk[CV()]
   ELSE NULL
     END,
-----------------------------------------------------------------------
min_dup[ANY] = min(dup)[ANY],
tmp_ch[ANY] = CASE WHEN t1_pk[CV()] = min_dup[1]
            THEN substr(tmp_str[CV()],0,
                               instr(tmp_str[CV()],',',1)-1)
       END,
-----------------------------------------------------------------------
tmp_cp[ANY] = min(tmp_ch)[ANY],
-----------------------------------------------------------------------
match[ANY] = CASE WHEN t1_pk[CV()] = min_dup[1] THEN tmp_cp[CV()]
                  ELSE match[CV()]
             END,
-----------------------------------------------------------------------
tmp_str[ANY]=CASE WHEN CT[CV()] IS NOT NULL
                  THEN REGEXP_REPLACE(ltrim(REPLACE(
                       tmp_str[CV()],tmp_cp[CV()] ),','),'[,]+',',')
           ELSE tmp_str[CV()]
             END,
-----------------------------------------------------------------------
ct_tmp[ANY] = CASE WHEN match[CV()] IS NULL AND t1_pk[CV()] IS NOT NULL
         THEN LENGTH(tmp_str[CV()])-
                       LENGTH(REPLACE(tmp_str[CV()],','))
         ELSE NULL
      END
);
     T1_PK T2_PK   UNMATCHE  STATUS
---------- -------- -------- ----------
         1 1                 MATCHED
         2 2                 MATCHED
         3 3                 MATCHED
         4 4                 MATCHED
         5 5                 MATCHED
         6 6                 MATCHED
         7                   NO T2
                    8,9,     NO T1                                             

8 rows selected.


11GR2, 用强大的递归WITH：
WITH  d AS (SELECT t1.pk pk1,t2.pk pk2,DENSE_RANK() OVER (ORDER BY t1.pk) rn,COUNT(DISTINCT t1.pk) OVER() cnt
             FROM t1,t2
            WHERE t2_compare BETWEEN t1_compare-2 AND t1_compare+2
            )
    , m AS (SELECT pk1,pk2,rn,cnt FROM d
             UNION ALL
            SELECT DISTINCT pk1,NULL,rn,cnt FROM d
           )
,t(rn,match_path,match_cnt,cnt) AS (
SELECT rn,TO_CHAR(pk1)||'-'||TO_CHAR(pk2),(CASE WHEN m.pk2 IS NULL THEN 0 ELSE 1 END),cnt
  FROM m
WHERE rn=1
UNION ALL
SELECT m.rn,t.match_path||','||m.pk1||'-'||m.pk2,t.match_cnt + (CASE WHEN m.pk2 IS NULL THEN 0 ELSE 1 END),t.cnt
  FROM t,m
WHERE t.rn<t.cnt
       AND t.rn+1=m.rn
       AND INSTR(match_path||',','-'||m.pk2||',')=0
)
SELECT match_path FROM (SELECT t.*,RANK() OVER(ORDER BY match_cnt DESC) rnk FROM T ) WHERE rnk=1;


MATCH_PATH
--------------------------------
1-2,2-1,3-4,4-3,5-6,6-5
1-1,2-3,3-2,4-4,5-5,6-6
1-1,2-2,3-3,4-4,5-5,6-6
1-2,2-1,3-3,4-4,5-5,6-6
1-1,2-2,3-4,4-3,5-5,6-6
1-2,2-1,3-4,4-3,5-5,6-6
1-1,2-3,3-2,4-4,5-6,6-5
1-1,2-2,3-3,4-4,5-6,6-5
1-2,2-1,3-3,4-4,5-6,6-5
1-1,2-2,3-4,4-3,5-6,6-5

10 rows selected.

kachau

赞一个！高人高人

newkid

http://oraqa.com/2010/07/05/how- ... equence-lcs-in-sql/

How to find the Longest Common Subsequence (LCS) in SQL

找出同一组字符串中最长的公共子序列，这个子序列的每个字符在每个字符串中都是以相同的先后顺序出现的（不一定连续）。

July 5th, 2010 By Frank Zhou

The following is an interesting problem posted on the programming praxis website:

Longest Common Subsequence
Finding the longest common subsequence of two sequences is a classic computer science problem with an equally
classic solution that dates to the folklore of computing. The longest common subsequence is the longest set of
elements that appear in order (not necessarily contiguous) in two sequences, the solution can be used in matching DNA sequences and it is also the basis of Unix “DIFF” utility.

The following SQL pattern can be used to find the Longest Common Subsequences in different group of strings.
COLUMN Largest_Common_Sequences FORMAT  A38
COLUMN in_str FORMAT  A18
CREATE TABLE  DATA AS
(Select 1 as id, 10 as grp_id, 'ABRACADABRA'       as in_str from dual
union all
select 2 as id, 10 as grp_id, 'BARRACUDA'          as in_str from dual
union all
select 3 as id, 20 as grp_id, 'HHTHHTHHT'          as in_str from dual
union all
select 4 as id, 20 as grp_id, 'THHTHTTHT'          as in_str from dual
union all
select 5 as id, 30 as grp_id, 'PROGRAMMING'        as in_str from dual
union all
select 6 as id, 30 as grp_id, 'PRAXIS'             as in_str from dual
union all
select 7 as id, 40 as grp_id, 'HUMAN'              as in_str from dual
union all
select 8 as id, 40 as grp_id, 'CHIMPANZEE'         as in_str from dual
union all
select 9 as id, 50 as grp_id,  '!T@E#N$o%n^e'      as in_str from dual
union all
select 10 as id, 50 as grp_id, 'TE*No()n+e{'       as in_str from dual
union all
select 11 as id, 50 as grp_id, '=T8EN7o?ne'        as in_str from dual
);

--------------------------------------------------------SQL Solution------------------------------------------------------

WITH MAX_COM_SEQ  AS
(SELECT DISTINCT id, grp_id, in_str, seq_str
  FROM
    (SELECT a.*, length(seq_str) len, MAX(LENGTH(seq_str)) OVER (PARTITION BY grp_id) max_len
      FROM
      (SELECT a.*,COUNT(DISTINCT id) OVER (PARTITION BY grp_id,seq_str) seq_cnt
       FROM
       (SELECT a.*, REPLACE(SYS_CONNECT_BY_PATH(chr,','),',') seq_str
         FROM (SELECT *
                FROM (SELECT a.*,COUNT(DISTINCT id) OVER(PARTITION BY grp_id, chr) cnt_chr
                       FROM (SELECT a.*, trim(COLUMN_VALUE) chr, rownum as rn
                              FROM (SELECT data.*, COUNT(*) OVER (PARTITION BY grp_id) cnt FROM data ) a,
                                    xmltable(rtrim(REGEXP_REPLACE(a.in_str,'(.)', '"\1",'), ','))
                             ) a
                     )
                WHERE cnt=cnt_chr
               ) a
         CONNECT BY id=PRIOR id AND rn > PRIOR rn
       ) a
      ) a
     WHERE cnt = seq_cnt
  )
  WHERE max_len = len
)
SELECT id, grp_id, in_str, CASE WHEN rank = 1 THEN '[ '|| STRAGG||' ]' END AS Largest_Common_Sequences
FROM
(SELECT id, grp_id, in_str, STRAGG, rank() OVER (PARTITION BY grp_id ORDER BY id ) AS RANK
  FROM
  (SELECT DISTINCT id, grp_id, in_str, LISTAGG(seq_str, '->') WITHIN GROUP (ORDER BY seq_str) OVER(PARTITION BY id) STRAGG
   FROM (SELECT * FROM MAX_COM_SEQ )
  )
);

        ID     GRP_ID IN_STR             LARGEST_COMMON_SEQUENCES
---------- ---------- ------------------ --------------------------------------
         1         10 ABRACADABRA        [ ARACDA->BRACDA ]
         2         10 BARRACUDA
         3         20 HHTHHTHHT          [ HHTHTHT->THHTHHT ]
         4         20 THHTHTTHT
         5         30 PROGRAMMING        [ PRAI ]
         6         30 PRAXIS
         7         40 HUMAN              [ HMAN ]
         8         40 CHIMPANZEE
         9         50 !T@E#N$o%n^e       [ TENone ]
        10         50 TE*No()n+e{
        11         50 =T8EN7o?ne

11 rows selected.
SQL>

11GR2的递归WITH: 之所以不用SYS_CONNECT_BY_PATH是因为我看到数据中有很不规则的字符，因此很难找一个特殊字符来做分隔符。周兄还是用了逗号做分隔。
WITH d AS (
    SELECT dt.*,COUNT(DISTINCT id) OVER(PARTITION BY grp_id,c) cnt_c
      FROM (SELECT dt.*,SUBSTR(in_str,rn,1) c,rn
              FROM (SELECT data.*,COUNT(*) OVER (PARTITION BY grp_id) cnt FROM data) dt
                  ,(SELECT ROWNUM rn FROM (SELECT MAX(LENGTH(in_str)) len FROM data) CONNECT BY ROWNUM<=len)
             WHERE rn<=LENGTH(in_str)
            ) dt
)
,t(id,grp_id,in_str,rn,w,cnt) AS (
    SELECT id,grp_id,in_str,rn,c,cnt FROM d
    UNION ALL
    SELECT d.id,d.grp_id,d.in_str,d.rn,t.w||d.c,t.cnt
      FROM t,d
     WHERE t.id = d.id AND t.rn<d.rn
)
SELECT grp_id,w
  FROM (SELECT grp_id,w,rank() OVER(PARTITION BY grp_id ORDER BY LENGTH(w) DESC) rnk
         FROM t
         GROUP BY grp_id,w
         HAVING COUNT(DISTINCT id) = MAX(cnt)
        )
WHERE rnk=1
;

    GRP_ID W
---------- ------------
        10 ARACDA
        10 BRACDA
        20 HHTHTHT
        20 THHTHHT
        30 PRAI
        40 HMAN
        50 TENone

〇〇

５５和４７的区别是？

newkid

原帖由 〇〇 于 2010-7-7 13:40 发表
５５和４７的区别是？

#47要求连续而#55不要求。

比如 ABCD 和 ABEFD, #47要求答案是 AB, #55则是ABD.

dingjun123

这个有的看的了！~newkid is very strong man!~

casper0511

学习思路~ 同时感慨一下和高手的差距~

cj402444206

http://oraqa.com/2008/03/27/how- ... ombo-puzzle-in-sql/

How to solve the Stamp Combo Puzzle in SQL

邮票谜题：
父亲需要些1分，2分，3分，5分，10分的邮票，其中两种各买四张，另外的三种各买三张。我忘记是哪几种了。他给了我一些10分硬币，金额刚好买这些邮票。

March 27th, 2008 By Frank Zhou

The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:

“Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent stamps.
He said to get four each of two sorts and three each of the others,
but I’ve forgotten which. He gave me exactly enough to buy them; just these dimes.”
How many stamps of each type does Dad want? A dime is worth ten cents.


------------------------------10G SQL Solution-----------------------------
SELECT    '1*'||C1.CNT
       ||'+2*'||C2.CNT
       ||'+3*'||C3.CNT
       ||'+5*'||C4.CNT
       ||'+10*'||C5.CNT AS RESULT
FROM  (SELECT LEVEL CNT FROM DUAL WHERE LEVEL BETWEEN  3 AND 4 CONNECT BY LEVEL <=4) C1,
       (SELECT LEVEL CNT FROM DUAL WHERE LEVEL BETWEEN  3 AND 4 CONNECT BY LEVEL <=4) C2,
       (SELECT LEVEL CNT FROM DUAL WHERE LEVEL BETWEEN  3 AND 4 CONNECT BY LEVEL <=4) C3,
       (SELECT LEVEL CNT FROM DUAL WHERE LEVEL BETWEEN  3 AND 4 CONNECT BY LEVEL <=4) C4,
       (SELECT LEVEL CNT FROM DUAL WHERE LEVEL BETWEEN  3 AND 4 CONNECT BY LEVEL <=4) C5
WHERE   C1.CNT+C2.CNT+C3.CNT+C4.CNT+C5.CNT=4*2+3*3
  AND   MOD((1*C1.CNT+2*C2.CNT+3*C3.CNT+5*C4.CNT+10*C5.CNT),10)=0;