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

newkid

原帖由 qingyun 于 2010-6-26 22:23 发表
呵呵，我遇到一个实际工作中用到的算法，不知道这里有没有类似的：

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

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


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

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

搞一些具体例子我们来研究。

newkid

用11GR2的递归WITH解#29的邮票问题：
WITH t(lvl,val,left_4,left_3,result) AS (
  SELECT 0,0,2,3,'' FROM DUAL
  UNION ALL
  SELECT t.lvl+1
        ,t.val+s.price*cnt
        ,left_4 - DECODE(cnt,4,1,0)
        ,left_3 - DECODE(cnt,3,1,0)
        ,t.result||' '||s.price||'*'||cnt
    FROM t
        ,(SELECT ROWNUM price_id,DECODE(ROWNUM,4,5,5,10,ROWNUM) AS price FROM DUAL CONNECT BY ROWNUM<=5) s
        ,(SELECT 4 as cnt FROM DUAL UNION ALL SELECT 3 FROM DUAL)
   WHERE t.lvl+1=s.price_id
         AND (cnt=4 AND left_4>0 OR cnt=3 AND left_3>0)
   )
SELECT result||'='||val
FROM t
WHERE lvl=5 AND MOD(val,10)=0;


RESULT||'='||VAL
----------------------------------
1*3 2*4 3*3 5*4 10*3=70


WITH c  AS (SELECT 3 cnt FROM DUAL UNION ALL SELECT 4 FROM DUAL)
,stamps AS (SELECT c1.cnt||c2.cnt||c3.cnt||c5.cnt||c10.cnt AS all_cnt
                  ,c1.cnt+2*c2.cnt+3*c3.cnt+5*c5.cnt+10*c10.cnt AS val
                  ,'1*'||c1.cnt||'+2*'||c2.cnt||'+3*'||c3.cnt||'+5*'||c5.cnt||'+10*'||c10.cnt AS result
              FROM c c1,c c2,c c3,c c5,c c10
            )
SELECT result||'='||val from stamps
WHERE MOD(val,10)=0
      AND LENGTH(all_cnt)-LENGTH(REPLACE(all_cnt,'4'))=2
      AND LENGTH(all_cnt)-LENGTH(REPLACE(all_cnt,'3'))=3
      ;

RESULT||'='||VAL
-------------------------------------
1*3+2*4+3*3+5*4+10*3=70

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

junsansi

牛，学习

onano

研究的太深入了，学习

lihe_lihe1981

周凯吧.....新蛋的技术老大，目前在成都。。。。。。。。

小C量子

佩服中。。。

nyfor

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

我有做过类似的, 效率不咋的, 不过客户还能接受啦, 最终结果我不会算最优的, 我有要求用户提供一个终止算法的余料值.

newkid

我也来贴一个谜题：大数阶乘，比如400!的计算。

我以前做过的10G MODEL方法：
WITH tmp AS
        (SELECT *
           FROM (SELECT rn,col,prod
                  FROM (  SELECT ROWNUM rn
                            FROM DUAL
                          CONNECT BY ROWNUM<=400
                        )
                      ,(  SELECT ROWNUM col
                            FROM DUAL
                          CONNECT BY ROWNUM<=30
                        )               
                MODEL IGNORE NAV RETURN UPDATED ROWS
                DIMENSION BY (rn,col)
                MEASURES (0 prod )
                   RULES (
                   prod[any,any] order by rn,col=(CASE WHEN cv(rn)=1 AND cv(col)=1 THEN 1
                                                       ELSE MOD(prod[cv()-1,cv()],1E30)*cv(rn) + TRUNC(prod[cv(),cv()-1]/1E30)
                                                  END )
                   )
                )
         WHERE rn=400
        )
SELECT LTRIM(REPLACE(MAX(SYS_CONNECT_BY_PATH(LPAD(MOD(prod,1E30),30,'0'),'*')),'*'),'0') AS result
  FROM tmp
START WITH col=(SELECT MAX(col) FROM tmp WHERE prod>0)
CONNECT BY col = PRIOR col-1
/

RESULT
-----------------------------------------------
640345228466238952623479703195030058507025830260029594586844459428023971691868314362784786474632646762943505750358568108482981628835174352289619886468
029979373416541508381624264619423523070462443250151144486708906627739149181173319559964407095496713452904770203224349112107975932807951015453726672516
278778900093497637657103263503315339653498683868313393520243737881577867915063118587026182701698197400629830253085912983461622723045583395207596115053
022360868104332972551948526744322324386699484224042325998055516106359423769613992319171340638589965379701478272066063202173794720103213566246138090779
423045973606995675958360961587151299138222865785795493616176544804532220078258184008484364155912294542753848035583745180226759000613995601455952061272
11192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

新出炉的11GR2 递归WITH方法：
WITH t (n,str,result,roundup) AS (
SELECT 1,CAST('' AS VARCHAR2(4000)),CAST('1' AS VARCHAR2(4000)),0 FROM DUAL
UNION ALL
SELECT CASE WHEN str IS NULL THEN n+1 ELSE n END
      ,CASE WHEN str IS NULL THEN (CASE WHEN roundup=0 THEN '' ELSE TO_CHAR(roundup) END)||result
            WHEN LENGTH(str)>30 THEN SUBSTR(str,1,LENGTH(str)-30)
            ELSE ''
       END
      ,CASE WHEN str IS NULL THEN ''
            ELSE SUBSTR(TO_CHAR(TO_NUMBER(CASE WHEN LENGTH(str)>=30 THEN SUBSTR(str,-30)
                                                 ELSE str
                                          END)*n+roundup+1E30
                               )
                        ,-30)||result
       END
      ,CASE WHEN str IS NULL THEN 0
            ELSE TRUNC((TO_NUMBER(CASE WHEN LENGTH(str)>=30 THEN SUBSTR(str,-30)
                                       ELSE str
                                  END)*n+roundup
                        )/1E30)
       END
  FROM t
WHERE n<=400
) CYCLE n,result SET cycle_flag TO 'Y' DEFAULT 'N'  
SELECT LTRIM(result,'0') FROM t
WHERE n=400 AND str IS NULL;



LTRIM(RESULT,'0')
------------------------------------------------------------------------------------------------------------------------------------------------------
640345228466238952623479703195030058507025830260029594586844459428023971691868314362784786474632646762943505750358568108482981628835174352289619886468
029979373416541508381624264619423523070462443250151144486708906627739149181173319559964407095496713452904770203224349112107975932807951015453726672516
278778900093497637657103263503315339653498683868313393520243737881577867915063118587026182701698197400629830253085912983461622723045583395207596115053
022360868104332972551948526744322324386699484224042325998055516106359423769613992319171340638589965379701478272066063202173794720103213566246138090779
423045973606995675958360961587151299138222865785795493616176544804532220078258184008484364155912294542753848035583745180226759000613995601455952061272
11192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

newkid

http://oraqa.com/2008/01/19/how- ... nned-puzzle-in-sql/

How to solve the No Average Spanned Puzzle in SQL

给你一串数字，把它们重新排列后，使得不存在这样的情况：中间的某个数是前后两个数的平均值（这些数不一定相邻）。
比如数字串为1,2,3,4，则排列后不允许出现 1,2,4,3, 因为2在1和3的中间。

January 19th, 2008 By Frank Zhou

The following is an interesting puzzle posted by Jsoftware:

Arrange a list of distinct positive integers so that no two numbers have their average between them in the sequence.
COLUMN input  FORMAT A10
COLUMN reason FORMAT A60
variable input_data varchar2(20)
exec :input_data  := '1,2,3,4';

———Check if two number have their average between them in the sequence———
SELECT :input_data input,
PRIOR n||' is placed between '||CONNECT_BY_ROOT n||' and '||n as reason
FROM
(SELECT doc.extract('/l/text()').getNumberVal() n, ROWNUM rn
FROM
TABLE(xmlSequence(extract(XMLType('<doc><l>'||
      replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
)
WHERE LEVEL = 3
CONNECT BY PRIOR rn <rn
AND CASE WHEN LEVEL = 3
                    THEN CASE WHEN PRIOR n * 2 = n + CONNECT_BY_ROOT n
                                           THEN 1
                                 END
                   ELSE 1 END = 1
AND LEVEL <=3;

INPUT      REASON
---------- -----------------------------
1,2,3,4    2 is placed between 1 and 3
1,2,3,4    3 is placed between 2 and 4

——————————————10G SQL Solution————————————————
SELECT trim(BOTH ',' FROM str) AS No_Avg_Spanned_str
FROM
( WITH input AS
(SELECT doc.extract('/l/text()').getNumberVal() n, count(*) over () cnt
  FROM
  TABLE(xmlSequence(extract(XMLType('<doc><l>'||
  replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
),
  data AS
(SELECT sys_connect_by_path(n,',')||',' str
  FROM (SELECT n, cnt FROM input)
  WHERE LEVEL = cnt
  CONNECT BY NOCYCLE n != PRIOR n
  AND CASE WHEN LEVEL BETWEEN 3 AND cnt
                      THEN CASE WHEN PRIOR n * 2 != n + CONNECT_BY_ROOT n
                                             THEN 1 END
                      ELSE 1 END =1
  )
SELECT str FROM data
WHERE str NOT IN
(SELECT str
FROM
(SELECT str FROM data) a,
(SELECT CONNECT_BY_ROOT n as head, PRIOR n as pre_num, n as num
   FROM (SELECT n FROM input)
   WHERE LEVEL = 3
   CONNECT BY NOCYCLE PRIOR n != n
   AND CASE WHEN LEVEL = 3
                       THEN CASE WHEN PRIOR n * 2 = n + CONNECT_BY_ROOT n
                                              THEN 1
                                    END
                        ELSE 1 END = 1
   AND LEVEL <=3
  ) b
WHERE instr (str,','||pre_num||',') > instr(str, ','||b.head||',')
AND   instr (str,','||num||',') > instr(str, ','||pre_num||',')
)
);

NO_AVG_SPANNED_STR
--------------------
1,3,2,4
1,3,4,2
2,1,4,3
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,4,1,2
4,2,1,3
4,2,3,1

10 rows selected.

在和周兄讨论之后用11GR2递归WITH写的版本：
WITH input AS
    (SELECT doc.extract('/l/text()').getNumberVal() n, count(*) over () cnt
     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) AS
    (SELECT n,','||n||',',cnt,1,n
       FROM input
     UNION ALL
     SELECT input.n,t.str||input.n||',',input.cnt,lvl+1,t.root
       FROM t,input
      WHERE lvl<input.cnt
            AND INSTR(str,','||input.n||',')=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;


NO_AVG_SPANNED_STR
-----------------------------
4,2,3,1
1,3,4,2
1,3,2,4
3,1,4,2
3,1,2,4
3,4,1,2
2,1,4,3
2,4,1,3
2,4,3,1
4,2,1,3

10 rows selected.

zhangjiji7882

感觉对他来说，没有什么不可能，nothing is impossible