深夜独霸, 轮到我出个题目了——算24点的SQL解法

血月

关注

newkid

grubbyoo真是后生可畏，我看好你哟!

楼上各位的回复珠玉在前，等会有空好好研究一下，我先垫块砖：

create table t24 (n number);
INSERT INTO t24 VALUES (1);
INSERT INTO t24 VALUES (2);
INSERT INTO t24 VALUES (3);
INSERT INTO t24 VALUES (4);

create table o24 (o varchar2 (1));
INSERT INTO o24 VALUES ('+');
INSERT INTO o24 VALUES ('-');
INSERT INTO o24 VALUES ('*');
INSERT INTO o24 VALUES ('/');

COMMIT;

WITH vw_tmp AS (
     SELECT DECODE(o1.o,'+',a.n+b.n
                       ,'-',a.n-b.n
                       ,'*',a.n*b.n
                       ,'/',DECODE(b.n,0,NULL,a.n/b.n)
                  ) AS ab
           ,DECODE(o2.o,'+',b.n+c.n
                       ,'-',b.n-c.n
                       ,'*',b.n*c.n
                       ,'/',DECODE(c.n,0,NULL,b.n/c.n)
                  ) AS bc
           ,DECODE(o3.o,'+',c.n+d.n
                       ,'-',c.n-d.n
                       ,'*',c.n*d.n
                       ,'/',DECODE(d.n,0,NULL,c.n/d.n)
                  ) AS cd
           ,a.n  as a
           ,o1.o as o1
           ,b.n  as b
           ,o2.o as o2
           ,c.n  as c
           ,o3.o as o3
           ,d.n  as d
       from t24 a, t24 b,t24 c,t24 d,o24 o1,o24 o2,o24 o3
      WHERE a.rowid NOT IN (b.rowid,c.rowid,d.rowid)
            AND b.rowid NOT IN (c.rowid,d.rowid)
            AND c.rowid<>d.rowid
     )
    ,vw_tmp2 AS (
    SELECT vw_tmp.*
          ,DECODE( o2,'+',ab+c
                     ,'-',ab-c
                     ,'*',ab*c
                     ,'/',DECODE(c,0,NULL,ab/c)
                  ) AS ab_c
          ,DECODE( o1,'+',a+bc
                     ,'-',a-bc
                     ,'*',a*bc
                     ,'/',DECODE(bc,0,NULL,a/bc)
                  ) AS a_bc
          ,DECODE( o3,'+',bc+d
                     ,'-',bc-d
                     ,'*',bc*d
                     ,'/',DECODE(d,0,NULL,bc/d)
                  ) AS bc_d
          ,DECODE( o2,'+',b+cd
                     ,'-',b-cd
                     ,'*',b*cd
                     ,'/',DECODE(cd,0,NULL,b/cd)
                  ) AS b_cd
     FROM vw_tmp
        )
    ,vw_tmp3 AS (
    SELECT '(('||a||o1||b||')'||o2||c||')'||o3||d as formula
          ,DECODE( o3,'+',ab_c+d
                     ,'-',ab_c-d
                     ,'*',ab_c*d
                     ,'/',DECODE(d,0,NULL,ab_c/d)
                  ) AS result
     FROM vw_tmp2
    UNION ALL
    SELECT '('||a||o1||'('||b||o2||c||'))'||o3||d as formula
          ,DECODE( o3,'+',a_bc+d
                     ,'-',a_bc-d
                     ,'*',a_bc*d
                     ,'/',DECODE(d,0,NULL,a_bc/d)
                  ) AS result
     FROM vw_tmp2
    UNION ALL
    SELECT '('||a||o1||b||')'||o2||'('||c||o3||d||')' as formula
          ,DECODE( o2,'+',ab+cd
                     ,'-',ab-cd
                     ,'*',ab*cd
                     ,'/',DECODE(cd,0,NULL,ab/cd)
                  ) AS result
     FROM vw_tmp2
    UNION ALL
    SELECT a||o1||'(('||b||o2||c||')'||o3||d||')' as formula
          ,DECODE( o1,'+',a+bc_d
                     ,'-',a-bc_d
                     ,'*',a*bc_d
                     ,'/',DECODE(bc_d,0,NULL,a/bc_d)
                  ) AS result
     FROM vw_tmp2
    UNION ALL
    SELECT a||o1||'('||b||o2||'('||c||o3||d||'))' as formula
          ,DECODE( o1,'+',a+b_cd
                     ,'-',a-b_cd
                     ,'*',a*b_cd
                     ,'/',DECODE(b_cd,0,NULL,a/b_cd)
                  ) AS result
     FROM vw_tmp2
   )
SELECT formula,result FROM vw_tmp3
WHERE result=24;

这是基于这样的思路：
1.穷尽所有操作数和操作符的排列
2.穷尽所有计算顺序的排列并对其求值，分为五大类：

  ((a b) c) d
  
  (a (b c)) d
  
  (a b) (c d)
  
  a ((b c) d)
  
  a (b (c d))

对第2点我觉得不太满意，也不知道有没有漏洞，基本上是个体力活，自己看着都要吐了。

在这基础上去除重复的思路也有，也是个体力活，等有空了写一下，希望不要把列位看官也看吐了。

newkid

去除括号比较好办，判断优先级就可以了；去除重复的思路是在可互换的情况下把操作数从小到大排列，用DISTINCT去掉。但是还有一些情况没判断出来。先这样吧，将就着看。

WITH v24 AS (SELECT id,n,MAX(SYS_CONNECT_BY_PATH(n,',')) OVER() as sorted
                   ,REGEXP_REPLACE(MAX(SYS_CONNECT_BY_PATH(n,',')) OVER(),'[^,]+','',1,id) AS sorted_ex
               FROM (SELECT ROWNUM id, n FROM (SELECT * FROM t24 ORDER BY n))
              START WITH id=1 CONNECT BY id=PRIOR id+1
             )
    ,vw_tmp AS (
     SELECT DECODE(o1.o,'+',a.n+b.n
                       ,'-',a.n-b.n
                       ,'*',a.n*b.n
                       ,'/',DECODE(b.n,0,NULL,a.n/b.n)
                  ) AS ab
           ,DECODE(o2.o,'+',b.n+c.n
                       ,'-',b.n-c.n
                       ,'*',b.n*c.n
                       ,'/',DECODE(c.n,0,NULL,b.n/c.n)
                  ) AS bc
           ,DECODE(o3.o,'+',c.n+d.n
                       ,'-',c.n-d.n
                       ,'*',c.n*d.n
                       ,'/',DECODE(d.n,0,NULL,c.n/d.n)
                  ) AS cd
           ,a.n  as a
           ,o1.o as o1
           ,b.n  as b
           ,o2.o as o2
           ,c.n  as c
           ,o3.o as o3
           ,d.n  as d
           ,a.sorted
           ,a.sorted_ex as a_ex
           ,d.sorted_ex as d_ex
       from v24 a, v24 b,v24 c,v24 d,o24 o1,o24 o2,o24 o3
      WHERE a.id NOT IN (b.id,c.id,d.id)
            AND b.id NOT IN (c.id,d.id)
            AND c.id<>d.id
     )
    ,vw_tmp2 AS (
    SELECT vw_tmp.*
          ,o1||o2||o3 as op
          ,DECODE(o1,'+',1,'-',1,2) AS p1
          ,DECODE(o2,'+',1,'-',1,2) AS p2
          ,DECODE(o3,'+',1,'-',1,2) AS p3
          ,DECODE( o2,'+',ab+c
                     ,'-',ab-c
                     ,'*',ab*c
                     ,'/',DECODE(c,0,NULL,ab/c)
                  ) AS ab_c
          ,DECODE( o1,'+',a+bc
                     ,'-',a-bc
                     ,'*',a*bc
                     ,'/',DECODE(bc,0,NULL,a/bc)
                  ) AS a_bc
          ,DECODE( o3,'+',bc+d
                     ,'-',bc-d
                     ,'*',bc*d
                     ,'/',DECODE(d,0,NULL,bc/d)
                  ) AS bc_d
          ,DECODE( o2,'+',b+cd
                     ,'-',b-cd
                     ,'*',b*cd
                     ,'/',DECODE(cd,0,NULL,b/cd)
                  ) AS b_cd
     FROM vw_tmp
        )
    ,vw_tmp3 AS (  ---- ((a b) c) d
    SELECT CASE WHEN p2<p3 THEN '(' END
           ||CASE WHEN p1<p2 THEN '(' END
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,1)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,1)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(LEAST(a,b))
                  ELSE TO_CHAR(a)
             END
           ||o1
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,2)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,2)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(GREATEST(a,b))
                  ELSE TO_CHAR(b)
             END
           ||CASE WHEN p1<p2 THEN ')' END
           ||o2
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,3)
                  WHEN o1||o2 IN ('**','++') THEN REGEXP_SUBSTR(d_ex,'[^,]',1,3)
                  ELSE TO_CHAR(c)
             END
           ||CASE WHEN p2<p3 THEN ')' END
           ||o3
           ||CASE WHEN op IN ('***','+++') THEN REGEXP_SUBSTR(sorted,'[^,]',1,4)
                  ELSE TO_CHAR(d)
             END
           as formula
          ,DECODE( o3,'+',ab_c+d
                     ,'-',ab_c-d
                     ,'*',ab_c*d
                     ,'/',DECODE(d,0,NULL,ab_c/d)
                  ) AS result
     FROM vw_tmp2
    UNION ALL    ---- (a (b c)) d
    SELECT CASE WHEN p1<p3 THEN '(' END
           ||a
           ||o1
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN '(' END
           ||CASE WHEN o2 IN ('*','+') THEN LEAST(b,c)
                  ELSE b
             END
           ||o2
           ||CASE WHEN o2 IN ('*','+') THEN GREATEST(b,c)
                  ELSE c
             END
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN ')' END
           ||CASE WHEN p1<p3 THEN ')' END
           ||o3
           ||d as formula
          ,DECODE( o3,'+',a_bc+d
                     ,'-',a_bc-d
                     ,'*',a_bc*d
                     ,'/',DECODE(d,0,NULL,a_bc/d)
                  ) AS result
     FROM vw_tmp2
    WHERE o1 NOT IN ('*','+')
    UNION ALL   ---- a ((b c) d)
    SELECT a
           ||o1
           ||CASE WHEN p3<p1 OR p3=p1 AND o1 IN ('/','-') THEN '(' END
           ||CASE WHEN p2<p3 THEN '(' END
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,1)
                  WHEN o2 IN ('*','+') THEN TO_CHAR(LEAST(b,c))
                  ELSE TO_CHAR(b)
             END
           ||o2
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,2)
                  WHEN o2 IN ('*','+') THEN TO_CHAR(GREATEST(b,c))
                  ELSE TO_CHAR(c)
             END
           ||CASE WHEN p2<p3 THEN ')' END
           ||o3
           ||CASE WHEN o2||o3 IN ('**','++') THEN REGEXP_SUBSTR(a_ex,'[^,]',1,3)
                  ELSE TO_CHAR(d)
             END
           ||CASE WHEN p3<p1 OR p3=p1 AND o1 IN ('/','-') THEN ')' END
           as formula
          ,DECODE( o1,'+',a+bc_d
                     ,'-',a-bc_d
                     ,'*',a*bc_d
                     ,'/',DECODE(bc_d,0,NULL,a/bc_d)
                  ) AS result
     FROM vw_tmp2
    WHERE o1 NOT IN ('*','+')
    UNION ALL  ---- a (b (c d))
    SELECT a
           ||o1
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN '(' END
           ||b
           ||o2
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN '(' END
           ||CASE WHEN o3 IN ('*','+') THEN LEAST(c,d)
                  ELSE c
             END
           ||o3
           ||CASE WHEN o3 IN ('*','+') THEN GREATEST(c,d)
                  ELSE d
             END
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN ')' END
           ||CASE WHEN p2<p1 OR p2=p1 AND o1 IN ('/','-') THEN ')' END
           as formula
          ,DECODE( o1,'+',a+b_cd
                     ,'-',a-b_cd
                     ,'*',a*b_cd
                     ,'/',DECODE(b_cd,0,NULL,a/b_cd)
                  ) AS result
     FROM vw_tmp2
    WHERE o1 NOT IN ('*','+') AND o2 NOT IN ('*','+')
    UNION ALL    ---- (a b) (c d)
    SELECT CASE WHEN p1<p2 THEN '(' END
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,1)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(LEAST(a,b))
                  ELSE TO_CHAR(a)
             END
           ||o1
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,2)
                  WHEN o1 IN ('*','+') THEN TO_CHAR(GREATEST(a,b))
                  ELSE TO_CHAR(b)
             END
           ||CASE WHEN p1<p2 THEN ')' END
           ||o2
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN '(' END
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,3)
                  WHEN o3 IN ('*','+') THEN TO_CHAR(LEAST(c,d))
                  ELSE TO_CHAR(c)
             END
           ||o3
           ||CASE WHEN op IN ('+*+','*+*') THEN REGEXP_SUBSTR(sorted,'[^,]',1,4)
                  WHEN o3 IN ('*','+') THEN TO_CHAR(GREATEST(c,d))
                  ELSE TO_CHAR(d)
             END
           ||CASE WHEN p3<p2 OR p2=p3 AND o2 IN ('/','-') THEN ')' END
           as formula
          ,DECODE( o2,'+',ab+cd
                     ,'-',ab-cd
                     ,'*',ab*cd
                     ,'/',DECODE(cd,0,NULL,ab/cd)
                  ) AS result
     FROM vw_tmp2
    WHERE NOT (p1=p2 OR p2=p3 AND o2 IN ('+','*')) AND op<>'+*-'
   )
SELECT DISTINCT formula FROM vw_tmp3
WHERE result=24;



[ 本帖最后由 newkid 于 2008-10-7 00:09 编辑 ]

newkid

grubbyoo的算法和我的对应如下（帮他改了几个笔误）:

1.先取 前2个数字n1,n2 分别计算加减乘除 得到c12，
2.再取第三个数字 n3，c12和n3分别计算 加减乘除 得到 c123，n2和n3加减乘除得到 c23
3.取第四个数字n4,  
  1.c123和n4做加减乘除 得到最后结果         ---- ((a b) c) d
  2.n3与n4的加减乘除再与c12做加减乘除  得到最后结果   --- (a b) (c d)
  3.c23与n4的加减乘除再与n1做加减乘除  得到最后结果   --- a ((b c) d)
  4.n3与n4 做除减运算，再与n2,与n1做除减计算     --- a (b (c d))

有一种情况没有覆盖到:
(a (b c)) d
即c23先和n1运算，再和n4运算。

理论上讲这种情况被其他的包含了吗？比如(a-(b/c))*d在其他排列中能否出现？

nyfor

好复杂, 太佩服了!为这种研究精神鼓掌, 加个精华.

grubbyoo

原帖由 newkid 于 2008-9-25 04:33 发表
grubbyoo的算法和我的对应如下（帮他改了几个笔误）:

1.先取 前2个数字n1,n2 分别计算加减乘除 得到c12，
2.再取第三个数字 n3，c12和n3分别计算 加减乘除 得到 c123，n2和n3加减乘除得到 c23
3.取第四个数字n4,  
  1.c123和n4做加减乘除 得到最后结果         ---- ((a b) c) d
  2.n3与n4的加减乘除再与c12做加减乘除  得到最后结果   --- (a b) (c d)
  3.c23与n4的加减乘除再与n1做加减乘除  得到最后结果   --- a ((b c) d)
  4.n3与n4 做除减运算，再与n2,与n1做除减计算     --- a (b (c d))

有一种情况没有覆盖到:
(a (b c)) d
即c23先和n1运算，再和n4运算。

理论上讲这种情况被其他的包含了吗？比如(a-(b/c))*d在其他排列中能否出现？

真是思维缜密，我还是漏了，好好学学你的代码

zhangweicai74

原帖由 nyfor 于 2008-9-25 08:50 发表
好复杂, 太佩服了!为这种研究精神鼓掌, 加个精华.

NEWKID 都要成OLDMAN了
终于得了个精华,恭喜

smallnavy

支持这种研究精神，建议楼主把重要研究结果更新到顶楼，方便大家查阅。

dingjun123

佩服之至也！newkid的确够猛！

nyfor

原帖由 zhangweicai74 于 2008-9-25 11:02 发表

NEWKID 都要成OLDMAN了
终于得了个精华,恭喜

潜水厉害, 否则, 精华是大大的有