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

〇〇

40 exec :input_data  := '1,1,2,3,3,4';

newkid

原帖由 〇〇 于 2010-7-1 21:39 发表
40 exec :input_data  := '1,1,2,3,3,4';

原题目说  a list of distinct positive integers ，也就是不重复的。

〇〇

英语不好害死人啊

newkid

有重复的也很容易，构造一个唯一的ID就是了：
WITH input AS
    (SELECT doc.extract('/l/text()').getNumberVal() n, count(*) over () cnt,ROWNUM id
     FROM
     TABLE(xmlSequence(extract(XMLType('<doc><l>'||
     replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
    )
,t2(n1,n2,n3,lvl) AS (
    SELECT n,0,0,1 FROM input
    UNION ALL
    SELECT t2.n1
          ,DECODE(lvl,1,input.n,t2.n2)
          ,DECODE(lvl,2,input.n,t2.n3)
          ,lvl+1
      FROM t2,input
     WHERE lvl<3 AND input.n NOT IN (n1,n2)
    )
,b AS (SELECT n1,n2,n3 from t2 WHERE lvl=3 AND n2*2=n1+n3)
,t(n,str,cnt,lvl,root,all_ids) AS
    (SELECT n,','||n||',',cnt,1,n,','||id||','
       FROM input
     UNION ALL
     SELECT input.n,t.str||input.n||',',input.cnt,lvl+1,t.root,t.all_ids||input.id||','
       FROM t,input
      WHERE lvl<input.cnt
            -- AND INSTR(str,','||input.n||',')=0 --- nocycle
            AND INSTR(all_ids,','||input.id||',')=0 --- nocycle
            AND (lvl<2 OR lvl>=2 AND t.n*2 != input.n + root)
            AND NOT EXISTS
                (SELECT 1
                  FROM b
                 WHERE instr(t.str||input.n||',', ','||b.n2||',') > instr(t.str||input.n||',', ','||b.n1||',')
                   AND instr(t.str||input.n||',', ','||b.n3||',') > instr(t.str||input.n||',', ','||n2||',')
                   AND instr(t.str||input.n||',', ','||b.n1||',') > 0
                )
    )
SELECT trim(BOTH ',' FROM str) AS No_Avg_Spanned_str
  FROM t
WHERE lvl=cnt;

newkid

http://oraqa.com/2007/09/09/how-to-solve-this-puzzle-in-sql/

How to solve this "Div9" Puzzle in SQL

1-9组成的9位数，每个数字出现一次，要求前N位可被N整除，N=1~9
比如：12345,
1可被1整除，12被2整除，123被3整除，1236被4整除，12365被5整除。

September 9th, 2007 By Frank Zhou

The following is an interesting puzzle posted by Jsoftware: Find a 9-digit number a[1]a[2]a[3]…. containing all the digits 1,2,…,9 such that “K” divides a[1]a[2]a[3]…..a[k] for each k = 1,2,3….9.

———————-SQL Solution—————
SQL> set timing on
SQL> set serveroutput on

SELECT TO_NUMBER( STR) NUM
FROM
(WITH NUM AS (SELECT LEVEL n FROM dual CONNECT BY LEVEL <= 9)
SELECT STR
FROM
(SELECT STR
FROM
(SELECT REPLACE(sys_connect_by_path( n,',' ),',') str
    FROM (SELECT  n FROM NUM) YourTable
  CONNECT by NOCYCLE n != PRIOR n
----- The following code can be used to speed up the performance,
----- The SQL Solution works without it.
--------------------------------------------------------------
  AND CASE WHEN LEVEL = 1
           THEN MOD (N, 2 )
           ELSE 1
      END  = 1
  AND CASE WHEN LEVEL = 5
           THEN MOD(N,5)
            ELSE 0
      END  = 0
------------------------------------------------------------
  AND CASE WHEN MOD(PRIOR N,2) = 0 AND MOD(N,2) = 1
           THEN 1
           WHEN MOD (PRIOR N,2) = 1 AND MOD(N,2) = 0
           THEN 1
          END = 1
)
WHERE length(str) = 9) A, (SELECT n FROM NUM) B
WHERE MOD(TO_NUMBER(SUBSTR(A.STR,0, B.n)),B.n) = 0
GROUP BY A.STR
HAVING COUNT(*) = 9
);

       NUM
----------
381654729

Elapsed: 00:00:00.06

在11GR2强大的递归WITH面前简直不堪一击：

WITH n AS (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9)
,t(lvl,path) AS (
SELECT 1,TO_CHAR(n) FROM n
UNION ALL
SELECT lvl+1,path||n
  FROM t,n
WHERE INSTR(path,n)=0
       AND MOD(path||n,lvl+1)=0
)
SELECT path FROM t WHERE lvl=9;

PATH
---------------------
381654729

Elapsed: 00:00:00.02

[ 本帖最后由 newkid 于 2010-7-7 23:54 编辑 ]

newkid

http://oraqa.com/2007/08/14/how- ... -of-strings-in-sql/

How to find the longest common substring pattern in different group of strings in SQL

找出每组数据(grp_id相同为同组)中最长的公共子串。

August 14th, 2007 By Frank Zhou

The following SQL pattern can be used to find the longest common substring pattern in different group of strings.
create table t8 as
Select 1 as id, 10 as grp_id,  'afpOnef1' as in_str from dual
union all
select 2 as id, 10 as grp_id,  '1Onez' as in_str from dual
union all
select 3 as id, 10 as grp_id,  '91Onez' as in_str from dual
union all
select 4 as id, 20 as grp_id,  'bptwoj' as in_str from dual
union all
select 5 as id ,20 as grp_id,  '9patwof' as in_str from dual
union all
select 6 as id ,20 as grp_id,  '+patwo3' as in_str from dual

COLUMN common_pattern FORMAT A28
COLUMN IN_STR FORMAT A18
-----------------------------------------------------10G SQL Solution----------------------------------------------------

SELECT DISTINCT id, grp_id, IN_STR, new_str common_pattern
FROM (SELECT id, grp_id,IN_STR, new_str, ct_str, cnt, length(new_str) len,
             MAX(LENGTH(new_str)) OVER (PARTITION BY grp_id) max_len
       FROM (SELECT id, grp_id, IN_STR, new_str, cnt,
                   COUNT(DISTINCT id) OVER (PARTITION BY grp_id, new_str) ct_str
              FROM(SELECT id, grp_id, IN_STR, rn, cnt,
      REPLACE(SYS_CONNECT_BY_PATH (ch,','),',') new_str
                     FROM (SELECT id,grp_id, IN_STR, ch, cnt,
                                  row_number( ) over (PARTITION BY
                                  grp_id,id ORDER BY rn) rn
                             FROM (SELECT id, grp_id,IN_STR, rownum rn,
                                          cnt,SUBSTR(IN_STR, LEVEL,1) ch
                                   FROM(SELECT id, grp_id, in_str,
        COUNT(id)OVER (PARTITION BY grp_id) cnt
     FROM  t8)
                                   CONNECT BY PRIOR id = id
                                   AND LEVEL <= LENGTH(IN_STR)
                                   AND PRIOR dbms_random.string('P',10)
                                       IS NOT NULL
                                  )
                          )
                      CONNECT BY PRIOR id = id
       AND PRIOR rn = rn -1
                  )
            )
           WHERE ct_str = cnt
     )
WHERE max_len = len
ORDER BY GRP_ID, ID;

        ID     GRP_ID IN_STR             COMMON_PATTERN
---------- ---------- ------------------ ----------------------------
         1         10 afpOnef1           One
         2         10 1Onez              One
         3         10 91Onez             One
         4         20 bptwoj             two
         5         20 9patwof            two
         6         20 +patwo3            two

6 rows selected.

我的写法：

SELECT id,grp_id,in_str,w
  FROM (SELECT t.*,rank() OVER(PARTITION BY grp_id ORDER BY LENGTH(w) DESC) rnk
          FROM (SELECT t.*,COUNT(DISTINCT id) OVER(PARTITION BY grp_id,w) cnt_w
                  FROM (SELECT t.*,REPLACE(SYS_CONNECT_BY_PATH(c,'/'),'/') w
                         FROM (SELECT *
                                 FROM (SELECT t.*,COUNT(DISTINCT id) OVER(PARTITION BY grp_id,c) cnt_c
                                         FROM (SELECT t.*,rn,SUBSTR(in_str,rn,1) c
                                                FROM (SELECT t8.*,COUNT(*) OVER (PARTITION BY grp_id) cnt FROM t8) t
                                                    ,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=100)
                                              ) t
                                       WHERE c IS NOT NULL
                                       )
                               WHERE cnt=cnt_c
                               ) t
                       CONNECT BY id=PRIOR id AND rn = PRIOR rn +1
                       ) t
                ) t
        WHERE cnt = cnt_w
        )
WHERE rnk=1;

比较了一下，和他的不同之处在于，我先把公共字符先过滤出来，再用它们拼接子串；而不是求出所有的子串。这样效率会高一些。

whmng

牛人呀，学习了

〇〇

"DBMS_RANDOM"."STRING"('P',10)在此的用途？

SQL> select "DBMS_RANDOM"."STRING"('P',10) from dual;

"DBMS_RANDOM"."STRING"('P',10)
------------------------------------------------------
{J;H>_JV=\

newkid

原帖由 〇〇 于 2010-7-2 15:49 发表
"DBMS_RANDOM"."STRING"('P',10)在此的用途？

SQL> select "DBMS_RANDOM"."STRING"('P',10) from dual;

"DBMS_RANDOM"."STRING"('P',10)
------------------------------------------------------
{J;H>_JV=\

最早是一个叫Laurent Schneider 的人提出来的，如果CONNECT BY里面没有PRIOR的话有时候会报错。但在这里的用法似乎又不是这样，等有空研究一下。

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