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

jiqing1004

太牛叉了~~~

newkid

http://oraqa.com/2008/06/16/how- ... parentheses-in-sql/

How to generate all strings of balanced parentheses in SQL

用SQL产生所有有效的括号配对方式。就是说左右括号一样多，右括号不能先出现。

June 16th, 2008 By Frank Zhou

The following SQL pattern can be used to generate all strings of balanced parentheses.

variable input number

—————————-SQL Solution ————————–
SELECT str
FROM
(SELECT CASE WHEN instr(str,')(') = 0
             THEN 'F'
             ELSE 'T' END flag, str FROM (SELECT rpad('()', &input * 2,'()') str from dual )
)
MODEL
DIMENSION BY (0 dim)
MEASURES(str, flag)
RULES ITERATE (10000) UNTIL (instr(str[ITERATION_NUMBER+1],')(') = 0 OR flag[0] = 'F')
(
str[ITERATION_NUMBER+1] =
CASE WHEN instr(str[cv()-1],')(') >0
      THEN CASE WHEN instr(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'()')>0
                THEN rpad('()',least(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')),
                                length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')))*2,'()')
                    ||CASE WHEN length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')) =
                                least(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')')),
                                length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')))
                           THEN rpad(')', abs(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')'))
                                 - length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'(')) ),')')
                           ELSE rpad('(', abs(length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),')'))
                                 - length(replace(substr(str[cv()-1],1,instr(str[cv()-1],')(')-1),'('))),'(')
                       END||'()'||substr(str[cv()-1], instr(str[cv()-1],')(')+2   )
                 ELSE substr(str[cv()-1],1,instr(str[cv()-1],')(')-1)||'()'||
                      substr(str[cv()-1],instr(str[cv()-1],')(')+2)
                END
END
);

Enter value for input: 5
old   5:              ELSE 'T' END flag, str FROM (SELECT rpad('()', &input * 2,'()') str from dual )
new   5:              ELSE 'T' END flag, str FROM (SELECT rpad('()', 5 * 2,'()') str from dual )

STR
----------
()()()()()
(())()()()
()(())()()
(()())()()
((()))()()
()()(())()
(())(())()
()(()())()
(()()())()
((())())()
()((()))()                                                                     

STR
----------
(()(()))()
((()()))()
(((())))()
()()()(())
(())()(())
()(())(())
(()())(())
((()))(())
()()(()())
(())(()())
()(()()())                                                                     

STR
----------
(()()()())
((())()())
()((())())
(()(())())
((()())())
(((()))())
()()((()))
(())((()))
()(()(()))
(()()(()))
((())(()))                                                                     

STR
----------
()((()()))
(()(()()))
((()()()))
(((())()))
()(((())))
(()((())))
((()(())))
(((()())))
((((()))))                                                                     

42 rows selected.

我用11GR2:
variable input number
exec :input :=5;

WITH
t (str,left_cnt,right_cnt) AS (
SELECT '(',1,0 FROM DUAL
UNION ALL
SELECT CAST(t.str||new_str AS VARCHAR2(20))
      ,left_cnt + DECODE(new_str,'(',1,0)
      ,right_cnt + DECODE(new_str,')',1,0)
FROM t,(SELECT '(' AS new_str FROM DUAL UNION ALL SELECT ')' AS new_str FROM DUAL)
WHERE new_str = '(' AND left_cnt<5
      OR new_str = ')' AND right_cnt<5 AND right_cnt<left_cnt
)
SELECT * FROM T WHERE left_cnt=5 AND right_cnt=5;

newkid

和上题类似，判断表达式中的括号匹配是否有效：

http://oraqa.com/2008/06/08/how- ... parentheses-in-sql/

How to determine if the formula string contains balanced pairs of parentheses in SQL

June 8th, 2008 By Frank Zhou

The following SQL pattern can be used to determine whether the formula/expression string contains balanced pairs of parentheses.
create table test as
select '( (1+2)*8 + ( (3+4)+(5+6) ) /9 ) * 9- (7+8)' str_num from dual
union all
select '( (1+2)+ (3+4) * 5 ) +6 ) ' str_num from dual ;

——————-SQL Solution —————-
SELECT old_str_num, flag as balanced_parentheses
FROM
(
SELECT str_num as old_str_num, rownum rn,
        regexp_replace(str_num,'[^()]') str_num
FROM test
)
MODEL
PARTITION BY (rn)
DIMENSION BY (0 dim)
MEASURES(old_str_num, str_num, CAST(NULL AS VARCHAR2(1)) flag )
RULES ITERATE (10000) UNTIL (str_num[0] IS NULL OR flag[0] = 'F')
(
flag[0] = CASE WHEN regexp_like(str_num[cv()],'^\(.*\)$')AND
                     (length(regexp_replace(str_num[cv()], '\(')) =
                      length(regexp_replace(str_num[cv()], '\)'))
                     )
                THEN 'T'
                ELSE 'F' END,
str_num[0] = CASE WHEN flag[0] = 'T'
                   THEN regexp_replace(str_num[cv()], '\(\)')
               END
);

OLD_STR_NUM                                   BALANCED_PARENTHESES
-------------------------------------------- -------------------------
( (1+2)*8 + ( (3+4)+(5+6) ) /9 ) * 9- (7+8)       T
( (1+2)+ (3+4) * 5 ) +6 )                         F

我的方法,不用递归:
WITH t AS (
SELECT str_num, REGEXP_REPLACE(str_num,'[^()]') AS str FROM test
)
SELECT str_num
      ,CASE WHEN MAX(left_cnt) = MAX(right_cnt) AND SUM(CASE WHEN right_cnt>left_cnt THEN 1 ELSE 0 END)=0
            THEN 'T'
            ELSE 'F'
       END AS flag
  FROM ( SELECT str_num,rn
               ,COUNT(CASE WHEN c='(' THEN 1 END) OVER(PARTITION BY str_num ORDER BY rn) left_cnt
               ,COUNT(CASE WHEN c=')' THEN 1 END) OVER(PARTITION BY str_num ORDER BY rn) right_cnt
           FROM (SELECT str_num,str,SUBSTR(str,rn,1) c,rn,LENGTH(str) l
                  FROM t,(SELECT ROWNUM rn FROM (SELECT MAX(LENGTH(str)) AS m FROM t) CONNECT BY ROWNUM<=m)
                 WHERE rn<=LENGTH(str)
                 )
        )
GROUP BY str_num
;

newkid

http://oraqa.com/2008/02/05/how- ... tion-puzzle-in-sql/

还是硬币问题。找到一个最小的数，无法用这个数目的硬币凑成一元。

How to solve the Impossible Combination Puzzle in SQL

February 5th, 2008 By Frank Zhou

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

What is the smallest number of coins that you can’t make a dollar with? i.e., for what N does there not exist a set of N coins adding up to a dollar? It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),
2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece), etc. It is not possible to make exactly a dollar with 101 coins.

———————————————-10G SQL Solution——————————————————
SELECT MIN (num) Min_Impossible_Combinations
FROM
(SELECT LEVEL num  FROM DUAL CONNECT BY LEVEL <=101
  MINUS
SELECT
  SUM(TO_NUMBER(SUBSTR(num,
           INSTR(num,',', 1, LEVEL) + 1,
           INSTR(num,',', 1, LEVEL+1) -
           INSTR(num,',', 1, LEVEL) -1))) num
FROM
(SELECT sys_connect_by_path(num,',')||',' num, rownum rn,
        regexp_replace(sys_connect_by_path(str_num,','),'[[:alpha:]]') ||',' AS str_num
FROM
(SELECT str_num, num, to_number(substr(str_num,0,length(str_num)-1)) n,
        substr(str_num,length(str_num)) coin_type
   FROM
(SELECT LEVEL||'A' str_num ,   LEVEL AS num
   FROM dual CONNECT BY LEVEL <=100
UNION ALL
SELECT LEVEL*5||'B' str_num,  LEVEL
   FROM dual CONNECT BY LEVEL*5 <=100
UNION ALL
SELECT LEVEL*10||'C' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*10 <=100
UNION ALL
SELECT LEVEL*25||'D' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*25 <=100
UNION ALL
SELECT LEVEL*50||'E' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*50<=100
UNION ALL
SELECT LEVEL*100||'F' str_num, LEVEL
   FROM dual CONNECT BY LEVEL*100<=100
)
)
WHERE
CASE LEVEL
WHEN  1 THEN CASE WHEN n = 100 THEN 1 END
WHEN  2 THEN CASE WHEN n + PRIOR  n =100 THEN 1 END
WHEN  3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n =100 THEN 1 END
ELSE  1 END =1
CONNECT BY PRIOR coin_type < coin_type
AND
CASE LEVEL
WHEN 2 THEN CASE WHEN n + PRIOR n <=100 THEN 1 END
WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=100 THEN 1 END
WHEN 4 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <96   THEN 1 END
WHEN 5 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=85  THEN 1 END
ELSE 1 END =1
AND LEVEL <6
)
CONNECT BY PRIOR rn = rn
AND INSTR (str_num,',', 1,LEVEL+1) > 0
AND PRIOR dbms_random.string('p',10) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(SUBSTR(str_num,
           INSTR(str_num,',', 1, LEVEL) + 1,
           INSTR(str_num,',', 1, LEVEL+1) -
           INSTR(str_num,',', 1, LEVEL) -1))) = 100
);

MIN_IMPOSSIBLE_COMBINATIONS
---------------------------
                         77

Elapsed: 00:00:08.06

我的解法就是利用1楼的递归写法：

WITH coins AS (
  SELECT 1 cents FROM DUAL
  UNION ALL SELECT 5 cents FROM DUAL
  UNION ALL SELECT 10 cents FROM DUAL
  UNION ALL SELECT 25 cents FROM DUAL
  UNION ALL SELECT 50 cents FROM DUAL
  )
,t(c1,c5,c10,c25,c50,cents,total_val) AS (
SELECT DECODE(c.cents,1,1,0)
      ,DECODE(c.cents,5,1,0)         
      ,DECODE(c.cents,10,1,0)         
      ,DECODE(c.cents,25,1,0)         
      ,DECODE(c.cents,50,1,0)         
      ,cents
      ,cents
  FROM coins c
UNION ALL
SELECT c1 + DECODE(c.cents,1,1,0)
      ,c5 + DECODE(c.cents,5,1,0)         
      ,c10+ DECODE(c.cents,10,1,0)         
      ,c25+ DECODE(c.cents,25,1,0)         
      ,c50+ DECODE(c.cents,50,1,0)         
      ,c.cents
      ,t.total_val + c.cents
  FROM t, coins c
WHERE t.total_val + c.cents<=100 AND t.cents<=c.cents
)
,t2 AS (
SELECT DISTINCT c1+c5+c10+c25+c50 cnt FROM t WHERE total_val=100
)
SELECT MIN(rn)
FROM (SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM<100
       )
WHERE NOT EXISTS (SELECT 1 FROM t2 WHERE cnt=rn);

或者：

WITH t AS (
SELECT /*+ materialize */ DISTINCT
        c1 .cnt
       +c5 .cnt
       +c10.cnt
       +c25.cnt
       +c50.cnt AS cnt
  FROM (SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=100)  c1  ---- 利用CONNECT BY构造出0～100作为1分硬币的个数
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=20 )  c5
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=10 )  c10
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=4  )  c25
      ,(SELECT ROWNUM-1 cnt FROM DUAL CONNECT BY ROWNUM-1<=2  )  c50
WHERE 1 *c1 .cnt
     +5 *c5 .cnt
     +10*c10.cnt
     +25*c25.cnt
     +50*c50.cnt=100
)
SELECT MIN(rn)                                          
FROM (SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM<100)
WHERE NOT EXISTS (SELECT 1 FROM t WHERE cnt=rn);

[ 本帖最后由 newkid 于 2010-6-29 03:43 编辑 ]

newkid

http://oraqa.com/2008/01/08/how- ... ing-problem-in-sql/

How to solve the Text Formatting Problem in SQL

字符串排版：每个词都由一个空格隔开，给定一个行宽，要求在适当的地方插入换行，使得每行不超过这个宽度。

January 8th, 2008 By Frank Zhou

The following is an interesting problem posted by Jsoftware:

Given: a string of words separated by blanks and a positive integer W of the desired width. Replace appropriate blanks in the string by the newline character, so that lines are no wider than W and each line contains all the words that fit within the line.

To focus on essentials, assume words are at most W in length, adjacent words are separated by exactly one blank, and the input string does not contain newlines.
create table t3 as
select 1 as id,
'Stop all the clocks, cut off the telephone, prevent the dog from barking with a juicy bone.
The quick brown fox jumps over the lazy dog. Assiduously avoid any and all asinine alliterations.'
as str from dual;

variable width number
exec :width := 25;

PL/SQL procedure successfully completed.

—————————————–SQL Solution——————-
SELECT regexp_replace(XMLAgg(XMLElement(X, str1||chr(10))
                                            ORDER BY root_rn),'<X>|</X><X>|</X>') DATA
FROM
(SELECT str1, id, root_rn
FROM
(SELECT max(str1) str1,  max(last_rn) as last_rn,  root_rn,  id
  FROM
  (SELECT ltrim(sys_connect_by_path(str,' ')) str1, rn AS last_rn,
   CONNECT_BY_ROOT rn AS root_rn, id
  FROM
  (SELECT doc.extract('/l/text()').getStringVal() str, id,
          row_number( ) over (partition by id order by rownum) as rn
     FROM t3, TABLE(xmlSequence(extract(XMLType('<doc><l>'||
              replace(str,' ','</l><l>')||'</l></doc>'),'/doc/l'))) doc
  )
  CONNECT BY PRIOR rn + 1 = rn
  AND PRIOR id = id
  AND LEVEL <= :width
)
WHERE length(str1) <= :width
GROUP BY id, root_rn
)
START WITH root_rn =1
CONNECT BY PRIOR last_rn + 1 = root_rn
AND PRIOR id = id
)
GROUP BY id;

DATA
---------------------------------
Stop all the clocks, cut
off the telephone,
prevent the dog from
barking with a juicy
bone. The quick brown fox
jumps over the lazy dog.
Assiduously avoid any and
all asinine
alliterations.

SQL> exec :width := 35;

PL/SQL procedure successfully completed.

SQL> /

DATA
--------------------------------------------
Stop all the clocks, cut off the
telephone, prevent the dog from
barking with a juicy bone. The
quick brown fox jumps over the lazy
dog. Assiduously avoid any and all
asinine alliterations.

我写的11GR2解法：
VAR v_width NUMBER;
EXEC :v_width :=35;

WITH t3 AS (
select 1 as id,
'Stop all the clocks, cut off the telephone, prevent the dog from barking with a juicy bone. The quick brown fox jumps over the lazy dog. Assiduously avoid any and all asinine alliterations.'
as str from dual
)
,t2 AS (
SELECT id,rn, REGEXP_SUBSTR(str,'[^ ]+',1,rn) str2
  FROM t3,(SELECT ROWNUM rn FROM (SELECT MAX(LENGTH(str)) m FROM t3) CONNECT BY ROWNUM<=m)
)
,t1 AS (
SELECT id,rn,str2,MAX(rn) OVER(PARTITION BY id) len
  FROM t2
WHERE str2 IS NOT NULL
)
,t (id,rn,str,cnt,len) AS (
SELECT id,1,str2,LENGTH(str2),len
FROM t1
WHERE rn=1
UNION ALL
SELECT t.id,t1.rn
      ,t.str||(CASE WHEN cnt+LENGTH(t1.str2)+1<=:v_width THEN ' ' ELSE CHR(10) END)||t1.str2
      ,CASE WHEN cnt+LENGTH(t1.str2)+1<=:v_width THEN cnt+LENGTH(t1.str2)+1
            ELSE LENGTH(t1.str2)
       END
      ,t.len
FROM t,t1
WHERE t.id = t1.id
      AND t.rn=t1.rn-1
)
SELECT id,str FROM t WHERE rn=len
;

        ID
----------
STR
-------------------------------------------------
         1
Stop all the clocks, cut off the
telephone, prevent the dog from
barking with a juicy bone. The
quick brown fox jumps over the lazy
dog. Assiduously avoid any and all
asinine alliterations.

newkid

http://oraqa.com/2007/12/16/how- ... hus-problem-in-sql/

How to solve the Josephus problem in SQL

n 个人围成一圈，每隔一人去掉一个，最后剩下来的是几号，去掉的人是按什么顺序？

December 16th, 2007 By Frank Zhou

The following is an interesting problem posted by Jsoftware:

With n people numbered 1 to n in a circle, every second one is eliminated until only one survives. Determine the elimination order and the survivor’s number.

—————————————–SQL Solution——————-
variable input_num  number
exec :input_num  := 10;
set timing on

SELECT trim(BOTH ','FROM regexp_replace(XMLAgg(XMLElement(X,
               CASE WHEN iteration IS NOT NULL THEN data END)
               ORDER BY rank),'<X>|</X><X>|</X>',',')) AS elimination_order,
              max(CASE WHEN iteration IS NULL THEN data END)
                      KEEP (DENSE_RANK LAST ORDER BY rank) survive_num
FROM
(SELECT row_number() OVER (ORDER BY iteration NULLS LAST, rn) rank,
                 data, iteration
FROM
(SELECT rn, data, iteration
   FROM
  (SELECT num, rn FROM
   (SELECT LEVEL num, LEVEL rn FROM dual CONNECT BY LEVEL <=:input_num)
  )
MODEL
DIMENSION BY (rn)
MEASURES
(num, num new_rank, CAST(NULL AS NUMBER) old_num,
CAST(NULL AS VARCHAR2(1)) flag, num data,
CAST(NULL AS NUMBER)  iteration, CAST(NULL AS NUMBER) cnt
)
RULES ITERATE(1000) UNTIL (cnt[1] = 1)
( flag[ANY]     = CASE iteration_number
                                       WHEN 0 THEN 'T'
                                      ELSE flag[CV()] END,
  new_rank[ANY] = CASE WHEN flag[cv()] = 'T'
                                               THEN CASE WHEN mod(new_rank[cv()],2) = 1
                                                                      THEN ceil(new_rank[cv()]/2) END
                                               ELSE CASE WHEN mod(new_rank[cv()],2) = 0
                                                                      THEN ceil(new_rank[cv()]/2) END
                                    END,
  old_num[ANY] = CASE WHEN new_rank[cv()] IS NULL AND
                                                         num[cv()] IS NOT NULL
                                            THEN num[cv()] END,
  num[ANY]     = CASE WHEN new_rank[cv()] IS NOT NULL
                                         THEN num[cv()] END,
  flag[ANY]    =   CASE WHEN max(old_num)[ANY] > max(num)[ANY]
                                      THEN 'T'
                                     ELSE 'F' END,
  cnt[1]       = count(num)[ANY],
  iteration[ANY] = CASE WHEN old_num[cv()] IS NOT NULL
                                            THEN iteration_number
                                            ELSE iteration[cv()]
                                 END
      )
   )
);
ELIMINATION_ORDER        SURVIVE_NUM
--------------------------        ------------
2,4,6,8,10,3,7,1,9                       5

Elapsed: 00:00:00.31

11GR2的递归WITH，厉害吧！
WITH t (cnt,people,pos,eliminated) AS (
   SELECT MAX(ROWNUM) cnt,MAX(SYS_CONNECT_BY_PATH(LPAD(ROWNUM,4),',')),6,''  FROM DUAL CONNECT BY ROWNUM<=:input_num
   UNION ALL
   SELECT cnt-1,SUBSTR(people,1,pos-1)||SUBSTR(people,pos+5)
         ,CASE WHEN pos+5<LENGTH(SUBSTR(people,1,pos-1)||SUBSTR(people,pos+5)) THEN pos+5
               WHEN pos+5<LENGTH(people) THEN 1
               ELSE 6
          END
         ,CAST(eliminated||SUBSTR(people,pos,5) AS VARCHAR2(200))
     FROM t
    WHERE cnt>1
   )
SELECT people,eliminated FROM t WHERE cnt=1;

PEOPLE
-------------------------------------------------------
ELIMINATED
-------------------------------------------------------
,   5
,   2,   4,   6,   8,  10,   3,   7,   1,   9

newkid

http://oraqa.com/2008/05/30/how- ... tion-puzzle-in-sql/

How to solve the 123456789 Equation Puzzle in SQL

May 30th, 2008 By Frank Zhou

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

In how many ways can “.” be replaced with “+”, “-”, or “” (concatenate) in .1.2.3.4.5.6.7.8.9 = 1 to form a correct equation?

——————————————-SQL Solution————————-
SELECT str_eq || ' = ' || output as output, count(*) over ( ) as counter
FROM
(select str_eq, XMLQuery( str_eq RETURNING CONTENT).getnumberval() output
FROM
(
  WITH DATA AS
  (
  SELECT doc.extract('/l/text()').getStringVal() chars
  FROM
  TABLE(xmlSequence(extract(XMLType('<doc><l>'||
  replace('+,-, ',',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
  )
SELECT replace(sys_connect_by_path(chars||to_char(LEVEL),'.'), '.') as str_eq
FROM ( SELECT chars from data)
WHERE LEVEL = 9
CONNECT BY LEVEL <= 9
)
)
where output = 1;

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
+1+2+3+4+5-6-7+8-9 = 1                         69                              
+1+2+3+4-5+6+7-8-9 = 1                         69                              
+1+2+3+45-67+8+9 = 1                           69                              
+1+2+3-4-5-6-7+8+9 = 1                         69                              
+1+2-3+4-5-6+7-8+9 = 1                         69                              
+1+2-3-4+5+6-7-8+9 = 1                         69                              
+1+2-3-4+5-6+7+8-9 = 1                         69                              
+1+2-34+56-7-8-9 = 1                           69                              
+1+23+4-5+67-89 = 1                            69                              
+1+23+45-67+8-9 = 1                            69                              
+1+23-4-5-6-7+8-9 = 1                          69                             

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
+1+23-45-67+89 = 1                             69                              
+1-2+3+4-5+6-7-8+9 = 1                         69                              
+1-2+3+4-5-6+7+8-9 = 1                         69                              
+1-2+3-4+5+6-7+8-9 = 1                         69                              
+1-2+34-56+7+8+9 = 1                           69                              
+1-2-3+4+5+6+7-8-9 = 1                         69                              
+1-2-3-4+5-6-7+8+9 = 1                         69                              
+1-2-3-4-5+6+7-8+9 = 1                         69                              
+1-2-3-45+67-8-9 = 1                           69                              
+1-23+4+5+6+7-8+9 = 1                          69                              
+1-23+45+67-89 = 1                             69                             

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
+1-23-4+5-67+89 = 1                            69                              
+1-23-45+67-8+9 = 1                            69                              
+12+34+5-67+8+9 = 1                            69                              
+12-34+5-6+7+8+9 = 1                           69                              
-1+2+3+4+5-6-7-8+9 = 1                         69                              
-1+2+3+4-5+6-7+8-9 = 1                         69                              
-1+2+3-4+5+6+7-8-9 = 1                         69                              
-1+2-3+4-5-6-7+8+9 = 1                         69                              
-1+2-3-4+5-6+7-8+9 = 1                         69                              
-1+2-3-4-5+6+7+8-9 = 1                         69                              
-1+23+4+5-6-7-8-9 = 1                          69                             

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
-1+23+45-67-8+9 = 1                            69                              
-1+23-4+5+67-89 = 1                            69                              
-1+23-4-5-6-7-8+9 = 1                          69                              
-1-2+3+4-5-6+7-8+9 = 1                         69                              
-1-2+3-4+5+6-7-8+9 = 1                         69                              
-1-2+3-4+5-6+7+8-9 = 1                         69                              
-1-2-3+4+5+6-7+8-9 = 1                         69                              
-1-2-3-4-5+6-7+8+9 = 1                         69                              
-1-23+4+5+6-7+8+9 = 1                          69                              
-12+34-5-6+7-8-9 = 1                           69                              
1+2+3+4+5-6-7+8-9 = 1                          69                             

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
1+2+3+4-5+6+7-8-9 = 1                          69                              
1+2+3+45-67+8+9 = 1                            69                              
1+2+3-4-5-6-7+8+9 = 1                          69                              
1+2-3+4-5-6+7-8+9 = 1                          69                              
1+2-3-4+5+6-7-8+9 = 1                          69                              
1+2-3-4+5-6+7+8-9 = 1                          69                              
1+2-34+56-7-8-9 = 1                            69                              
1+23+4-5+67-89 = 1                             69                              
1+23+45-67+8-9 = 1                             69                              
1+23-4-5-6-7+8-9 = 1                           69                              
1+23-45-67+89 = 1                              69                              

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
1-2+3+4-5+6-7-8+9 = 1                          69                              
1-2+3+4-5-6+7+8-9 = 1                          69                              
1-2+3-4+5+6-7+8-9 = 1                          69                              
1-2+34-56+7+8+9 = 1                            69                              
1-2-3+4+5+6+7-8-9 = 1                          69                              
1-2-3-4+5-6-7+8+9 = 1                          69                              
1-2-3-4-5+6+7-8+9 = 1                          69                              
1-2-3-45+67-8-9 = 1                            69                              
1-23+4+5+6+7-8+9 = 1                           69                              
1-23+45+67-89 = 1                              69                              
1-23-4+5-67+89 = 1                             69                             

OUTPUT                                    COUNTER                              
-------------------------------------- ----------                              
1-23-45+67-8+9 = 1                             69                              
12+34+5-67+8+9 = 1                             69                              
12-34+5-6+7+8+9 = 1                            69                              

69 rows selected.

这个题目其实就是野花发过的“丢失的符号”： http://www.itpub.net/thread-1301673-1-1.html

11GR2:
WITH n AS (SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10)
,o AS (SELECT '+' op FROM DUAL UNION ALL SELECT '-' op FROM DUAL UNION ALL SELECT NULL FROM DUAL)
,t(num,tot,expr,op) AS (
  SELECT 0 as num, 0 as tot, '' AS expr, '' AS op FROM DUAL
  UNION ALL
  SELECT n.rn
        ,DECODE(o.op,'+',t.tot+n.rn,'-',t.tot-n.rn,DECODE(t.op,'+',t.tot-t.num+t.num*10+n.rn,t.tot+t.num-t.num*10-n.rn))
        ,t.expr||o.op||n.rn
        ,o.op
    FROM n,t,o
   WHERE t.num = n.rn-1 AND (o.op IS NOT NULL OR t.op IS NOT NULL)
   )
SELECT expr||'='||tot AS OUTPUT
FROM t
WHERE num=9 AND tot=1;

其他解法：

WITH t AS(
SELECT '+' X FROM DUAL UNION ALL
SELECT '-' X FROM DUAL UNION ALL
SELECT ''  X FROM DUAL)
,t2 AS (
SELECT *
  FROM (SELECT ROWNUM id,t.x||
                         1||t1.x||
                         2||t2.x||
                         3||t3.x||
                         4||t4.x||
                         5||t5.x||
                         6||t6.x||
                         7||t7.x||
                         8||t8.x||
                         9 y
       FROM t,t t1,t t2,t t3,t t4,t t5,t t6,t t7,t t8
      WHERE t.x IN ('-','+')
      )
WHERE REPLACE(y,123)=y AND
      REPLACE(y,234)=y AND
      REPLACE(y,345)=y AND
      REPLACE(y,456)=y AND
      REPLACE(y,567)=y AND
      REPLACE(y,678)=y AND
      REPLACE(y,789)=y
)
SELECT LTRIM(y,'+')
  FROM (SELECT id,y,REGEXP_SUBSTR(y,'[+-]',1,rn) op,REGEXP_SUBSTR(y,'[^+-]+',1,rn) num
         FROM t2,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9)
        )
GROUP BY id,y
HAVING SUM(DECODE(op,'+',num,-num))=1
;


WITH t AS(
SELECT n,op
  FROM (SELECT '+' op FROM DUAL UNION ALL
        SELECT '-' op FROM DUAL UNION ALL
        SELECT ''  op FROM DUAL)
       ,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9)
WHERE n>1 OR op IN ('+','-')
)
,t2 AS (
SELECT ROWNUM id, REPLACE(SYS_CONNECT_BY_PATH(op||n,'@'),'@') y
  FROM t
WHERE n=9
START WITH n=1
CONNECT BY n= PRIOR n+1 AND (op IS NOT NULL OR PRIOR op IS NOT NULL)
)
SELECT LTRIM(y,'+')
  FROM (SELECT id,y,REGEXP_SUBSTR(y,'[+-]',1,rn) op,REGEXP_SUBSTR(y,'[^+-]+',1,rn) num
          FROM t2,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9)
        )
GROUP BY id,y
HAVING SUM(DECODE(op,'+',num,-num))=1
;


WITH t AS(
SELECT n,op
  FROM (SELECT '+' op FROM DUAL UNION ALL
        SELECT '-' op FROM DUAL UNION ALL
        SELECT '~'  op FROM DUAL)
       ,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9)
WHERE n>1 OR op IN ('+','-')
)
,t2 AS (
SELECT ROWNUM id, REPLACE(SYS_CONNECT_BY_PATH(op||n,'@'),'@') y
      ,DECODE(op,'+',n,'-',-n,DECODE(PRIOR op,'+',- (PRIOR n)+ (PRIOR n)*10 +n, (PRIOR n)- (PRIOR n)*10 -n)) val
  FROM t
WHERE n=9
START WITH n=1
CONNECT BY n= PRIOR n+1 AND (op <>'~' OR PRIOR op <>'~')
)
SELECT LTRIM(REPLACE(t2.y,'~'),'+')
  FROM t2,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9)
GROUP BY t2.y
HAVING SUM(DECODE(SUBSTR(y,(n-1)*2+1,1),'+',n,'-',-n,DECODE(SUBSTR(y,(n-2)*2+1,1),'+',-(n-1)+(n-1)*10+n,(n-1)-(n-1)*10-n )))=1;

newkid

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 max(fin_str) Stamp_combo
FROM
(SELECT ltrim(fin_str, ',') fin_str, rn, str_num
FROM
(SELECT sys_connect_by_path(str,', ') fin_str, rownum rn,
regexp_replace(sys_connect_by_path(str_num,','),'[[:alpha:]]') AS str_num
FROM
(SELECT str_num, str, substr(str_num,length(str_num)) stamp_type
FROM
(SELECT LEVEL||'A' str_num, LEVEL||' one_cent_stamp' AS str
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*2||'B' str_num, LEVEL||' two_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*3||'C' str_num, LEVEL||' three_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*5||'D' str_num, LEVEL||' five_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*10||'E' str_num, LEVEL||' ten_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
)
)
WHERE LEVEL = 5
CONNECT BY PRIOR stamp_type < stamp_type
)
WHERE length(regexp_replace(fin_str,'[^3]')) = 3
AND length(regexp_replace(fin_str,'[^4]')) = 2
)
CONNECT BY PRIOR rn = rn
AND regexp_substr(str_num,'[^,]+',1,LEVEL) IS NOT NULL
AND PRIOR dbms_random.string('p',20) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(regexp_substr(str_num,'[^,]+',1,LEVEL))) IN
(SELECT LEVEL FROM dual
WHERE mod(LEVEL,10) = 0
AND LEVEL >= (SELECT (1+2)*4 + (3+5+10)*3 FROM dual)
CONNECT BY LEVEL <=(SELECT (1+2+3) * 3 + (5+10) * 4 FROM dual)
);



STAMP_COMBO
------------------------------------------------------------------------------
3 one_cent_stamp, 4 two_cent_stamp, 3 three_cent_stamp, 4 five_cent_stamp, 3 ten_cent_stamp


—————————————————11G SQL Solution———————————————————-

SELECT fin_str AS  Stamp_combo
FROM
(SELECT ltrim(fin_str, ',') as fin_str, str_num
FROM
(SELECT sys_connect_by_path(str,', ') fin_str,
         regexp_replace(sys_connect_by_path(str_num,'+'),'[[:alpha:]]') AS str_num
  FROM
(SELECT str_num, str, substr(str_num,length(str_num)) stamp_type
  FROM
(SELECT LEVEL||'A' str_num, LEVEL||' one_cent_stamp' AS str
  FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
  UNION ALL
  SELECT LEVEL*2||'B' str_num, LEVEL||' two_cent_stamp'
  FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
  UNION ALL
  SELECT LEVEL*3||'C' str_num, LEVEL||' three_cent_stamp'
  FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
  UNION ALL
  SELECT LEVEL*5||'D' str_num, LEVEL||' five_cent_stamp'
  FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
  UNION ALL
  SELECT LEVEL*10||'E' str_num, LEVEL||' ten_cent_stamp'
  FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
)
)
WHERE LEVEL = 5
CONNECT BY PRIOR stamp_type < stamp_type
)
WHERE regexp_count(fin_str,'3') = 3
AND   regexp_count(fin_str,'4') = 2
)
WHERE XMLQuery(str_num RETURNING CONTENT).getnumberval()
IN
(SELECT LEVEL FROM dual
WHERE mod(LEVEL,10) = 0
AND LEVEL >=  XMLQuery('(1+2)*4 + (3+5+10)*3' RETURNING CONTENT).getnumberval()
CONNECT BY LEVEL <= XMLQuery('(1+2+3) * 3 + (5+10) * 4' RETURNING CONTENT).getnumberval()
);

STAMP_COMBO
——————————————————————————————————————————————
3 one_cent_stamp, 4 two_cent_stamp, 3 three_cent_stamp, 4 five_cent_stamp, 3 ten_cent_stamp



我的写法：
WITH stamps AS (
SELECT ROWNUM n
      ,(CASE WHEN ROWNUM IN (1,2) THEN 4 ELSE 3 END) AS m
      ,DECODE(ROWNUM,4,5,5,10,ROWNUM) val
  FROM DUAL
CONNECT BY ROWNUM<=5
)
,t1 AS (
SELECT id,n,TO_NUMBER(SUBSTR(t.m,stamps.n,1)) m
  FROM (SELECT ROWNUM id, m
          FROM (SELECT DISTINCT REPLACE(SYS_CONNECT_BY_PATH(m,','),',') m
                  FROM stamps
                 WHERE LEVEL=5
                CONNECT BY NOCYCLE n<>PRIOR n AND LEVEL<=5
                )
        ) t
      ,stamps
)
SELECT * FROM (
SELECT t1.id,t1.m,s.val,SUM(t1.m*s.val) OVER(PARTITION BY t1.id) total
  FROM t1,stamps s
WHERE t1.n = s.n
)
WHERE MOD(total,10)=0
ORDER BY id,val;

        ID          M        VAL      TOTAL
---------- ---------- ---------- ----------
         3          3          1         70
         3          4          2         70
         3          3          3         70
         3          4          5         70
         3          3         10         70

newkid

http://oraqa.com/2007/03/13/how- ... he-string-headtail/

在同一组(grp_id相同)的所有字符串(in_str)中，找出这组的最长的共有的头尾子串。


How to find the longest common substring patterns starting from the string head/tail

March 13th, 2007 By Frank Zhou

The following SQL pattern can be used to find the longest common substring patterns starting from the head/tail of the strings.
create table t5 as
Select 1 as id, 10 as grp_id,  'Fiveafpf1Three' as in_str from dual
union all
select 2 as id, 10 as grp_id,  'Five123zThree' as in_str from dual
union all
select 3 as id, 10 as grp_id,  'Five91OnezThree' as in_str from dual
union all
select 4 as id, 20 as grp_id,  'nine123TEN' as in_str from dual
union all
select 5 as id ,20 as grp_id,  'nine345TEN' as in_str from dual
SQL> select * from t5;

        ID     GRP_ID IN_STR
---------- ---------- ------------------
         1         10 Fiveafpf1Three
         2         10 Five123zThree
         3         10 Five91OnezThree
         4         20 nine123TEN
         5         20 nine345TEN   

-----------------------------------------------------------------------10G SQL Solution---------------------------------------------------
SELECT id, grp_id, IN_STR,
       CASE WHEN INSTR(IN_STR,HEAD,1) =INSTR(IN_STR,TAIL,-1)
          THEN HEAD ||'**'
   ELSE HEAD ||'**'||TAIL END AS Head_Tail_Pattern
FROM
(SELECT id, grp_id, IN_STR,
        MAX(CASE WHEN FLAG = 'HEAD'
          THEN common_pattern END) AS HEAD,
MAX(CASE WHEN FLAG = 'TAIL'
          THEN common_pattern END) AS TAIL
FROM
(
SELECT id, grp_id, IN_STR, new_str common_pattern , 'HEAD' AS Flag
   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,
                    COUNT(DISTINCT id) OVER (PARTITION BY grp_id, new_str) ct_str,
      COUNT(DISTINCT id) OVER (PARTITION BY grp_id) cnt
                  FROM (SELECT id, grp_id,IN_STR, SUBSTR(IN_STR,1,LEVEL) new_str
                         FROM t5
                        CONNECT BY PRIOR id = id
                        AND LEVEL <= LENGTH(IN_STR)
                        AND PRIOR dbms_random.string('P',10) IS NOT NULL
                       )
                )
          WHERE ct_str = cnt
      )
  WHERE max_len = len
  UNION ALL
  SELECT id, grp_id, REVERSE(IN_STR) IN_STR,
         REVERSE(new_str) common_pattern, 'TAIL' AS Flag
    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,
                   COUNT(DISTINCT id) OVER (PARTITION BY grp_id, new_str) ct_str,
     COUNT(DISTINCT id) OVER (PARTITION BY grp_id) cnt
                   FROM (SELECT id, grp_id,IN_STR, SUBSTR(IN_STR,1,LEVEL) new_str
                           FROM (SELECT id, grp_id, REVERSE(IN_STR) IN_STR
       FROM t5 )
                          CONNECT BY PRIOR id = id
                          AND LEVEL <= LENGTH(IN_STR)
                          AND PRIOR dbms_random.string('P',10) IS NOT NULL
                        )
                 )
           WHERE ct_str = cnt
        )
    WHERE max_len = len
)
GROUP BY GRP_ID, id, IN_STR
)
ORDER BY GRP_ID, id;

        ID     GRP_ID IN_STR             HEAD_TAIL_PATTERN
---------- ---------- ------------------ --------------------------------
         1         10 Fiveafpf1Three     Five**Three
         2         10 Five123zThree      Five**Three
         3         10 Five91OnezThree    Five**Three
         4         20 nine123TEN         nine**TEN
         5         20 nine345TEN         nine**TEN      


我的写法：
WITH t AS (
SELECT t5.*,MIN(LENGTH(in_str)) OVER(PARTITION BY grp_id) len FROM t5
)
SELECT DISTINCT id,grp_id,in_str
      ,MAX(CASE WHEN head_cnt=1 THEN head END) OVER(PARTITION BY grp_id)
      ,SUBSTR(MAX(CASE WHEN tail_cnt=1 THEN LPAD(rn,10)||tail END) OVER(PARTITION BY grp_id),11)
FROM (SELECT t2.*,COUNT(DISTINCT head) OVER(PARTITION BY grp_id,rn) head_cnt,COUNT(DISTINCT tail) OVER(PARTITION BY grp_id,rn) tail_cnt
        FROM (
      SELECT t.*,rn,SUBSTR(in_str,1,rn) head,SUBSTR(in_str,-rn) tail
        FROM t,(SELECT ROWNUM rn FROM (SELECT MAX(len) m FROM t) CONNECT BY ROWNUM<=m)
       WHERE rn<=t.len
             ) t2
      )
WHERE head_cnt=1 OR tail_cnt=1;

qingyun

呵呵，我遇到一个实际工作中用到的算法，不知道这里有没有类似的：

我曾经做过这个算法：
就是库存各个货位数量不等，现在需求出100数量，如何恰好凑出100；虽然是用plsql写的，不过主要是用的回溯算法，并不是纯SQL搞定的；

这个算法可以优化，就是把各个货位的数量先按相同的数量先合并分组，这样判断的循环次数能少很多，这个算法没实现。


另外，还有一个变异的算法：

  比如一块1m宽的钢板原料，切割成各种宽度条料，当日生产的条料有很多规格，里面有很多规格宽度相同，最终如何拼凑，才能最小范围的剩余余料；这个功能如今让客户自己拼凑；如果电脑计算，1.可能不是最优；2.可能太慢；
  我尝试用遗传算法模拟解决这个问题，不过变异的算法没掌握好。以后在研究吧。如今准备考OCP;
其实研究SQL算法，跟oracle的水平好像也没有太大关系了