puzzleup2012谜题，请用SQL或PLSQL解答

newkid

lastwinner 发表于 2012-9-20 01:45
我有个想法是螺旋向内切割，不知是否可行

我弄了个小图试一下，和纵向切割一样多。

newkid

第九题：写了个非递归SQL, 结果是17408种, 有待验证。

〇〇

newkid 发表于 2012-9-20 03:59
第九题：写了个非递归SQL, 结果是17408种, 有待验证。

所有种数/4？
加法乘法满足交换率，只算1种

newkid

〇〇 发表于 2012-9-20 05:50
所有种数/4？
加法乘法满足交换率，只算1种

不是这样吧？例子中是把乘法转换为除法。
我的SQL还是有重复的，明天继续。

〇〇

newkid 发表于 2012-9-20 06:55
不是这样吧？例子中是把乘法转换为除法。
我的SQL还是有重复的，明天继续。

我确实考虑不周

ryax

括号只与加减号有关系。

lastwinner

newkid 发表于 2012-9-20 02:32
我弄了个小图试一下，和纵向切割一样多。

脑子里转了一下，应该结果是一样的，反正都无法达到可切割线段总数量的1/2

ryax

12000左右

newkid

ryax 发表于 2012-9-20 17:06
括号只与加减号有关系。

例子不是说清楚了吗？A/(B/C)和A/B*C要算同一种。

因为算术操作符是二元操作，我们可以把相邻的操作数两两撮合，比如6个的：
(C1 C2) C3 C4 C5 C6
C1 (C2 C3) C4 C5 C6
C1 C2 (C3 C4) C5 C6
C1 C2 C3 (C4 C5) C6
C1 C2 C3 C4 (C5 C6)

这样就剩下5个操作数。如法炮制，有四种撮合法。再继续直至剩下一个，就是最后的表达式。
这已经覆盖了所有括号的添加方法，总共有 5*4*3*2*1=120种

这个过程虽然是递归的，但却是在列方向的递归；如果要用递归WITH来完成，只能用一个字符串来表示所有的列，可以想象写起来会相当复杂，我还没有去尝试。
如果不在列方向递归，做列转行是不行的，因为递归WITH无法合并两行数据为一行。

去除重复的思路有两种：
1.转换为从左到右的顺序，加上所有括号。
比如 A+B+C+D 必需写为 (((A+B)+C)+D)
难点在碰到 A+((B+C)+D)时也得转换为(((A+B)+C)+D)

2.转换为从左到右的顺序，去除多余括号
比如 A-((B*C)+D)，必需转换为A-B*C-D

我今天采用了方法2, SQL的结果是12608种。

newkid

先贴一下目前的SQL, 真是个体力活！

WITH
o AS (SELECT '+' op,0 pr FROM DUAL UNION ALL SELECT '-',0 FROM DUAL UNION ALL SELECT '*',1 FROM DUAL UNION ALL SELECT '/',1 FROM DUAL)
,d AS (
SELECT 'A' C1,'B' C2,'C' C3,'D' C4,'E' C5,'F' C6 FROM DUAL
)
,d5 AS (
SELECT C1||o.op||C2 C1,C3 C2,C4 C3,C5 C4,C6 C5
      ,o.pr c1pr,TO_NUMBER(NULL) c2pr,TO_NUMBER(NULL) c3pr,TO_NUMBER(NULL) c4pr,TO_NUMBER(NULL) c5pr --- 操作符优先级
      ,'@ 2' pos1,'@' pos2,'@' pos3,'@' pos4,'@' pos5 ---- 操作符在表达式中出现的位置
FROM d,o
UNION ALL
SELECT C1,C2||o.op||C3 C2,C4 C3,C5 C4,C6 C5
      ,TO_NUMBER(NULL) c1pr,o.pr c2pr,TO_NUMBER(NULL) c3pr,TO_NUMBER(NULL) c4pr,TO_NUMBER(NULL) c5pr
      ,'@' pos1,'@ 2' pos2,'@' pos3,'@' pos4,'@' pos5
FROM d,o
UNION ALL
SELECT C1,C2,C3||o.op||C4 C3,C5 C4,C6 C5
      ,TO_NUMBER(NULL) c1pr,TO_NUMBER(NULL) c2pr,o.pr c3pr,TO_NUMBER(NULL) c4pr,TO_NUMBER(NULL) c5pr
      ,'@' pos1,'@' pos2,'@ 2' pos3,'@' pos4,'@' pos5
  FROM d,o
UNION ALL
SELECT C1,C2,C3,C4||o.op||C5 C4,C6 C5
      ,TO_NUMBER(NULL) c1pr,TO_NUMBER(NULL) c2pr,TO_NUMBER(NULL) c3pr,o.pr c4pr,TO_NUMBER(NULL) c5pr
      ,'@' pos1,'@' pos2,'@' pos3,'@ 2' pos4,'@' pos5
  FROM d,o
UNION ALL
SELECT C1,C2,C3,C4,C5||o.op||C6 C5
      ,TO_NUMBER(NULL) c1pr,TO_NUMBER(NULL) c2pr,TO_NUMBER(NULL) c3pr,TO_NUMBER(NULL) c4pr,o.pr c5pr
      ,'@' pos1,'@' pos2,'@' pos3,'@' pos4,'@ 2' pos5
  FROM d,o
)
,d4 AS (
SELECT CASE WHEN c1pr<o.pr THEN '('||C1||')' ELSE C1 END
       ||o.op
       ||CASE WHEN c2pr<o.pr THEN '('||C2||')'
              WHEN c2pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C2,DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos2,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c2,SUBSTR(pos2,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)
                   ||SUBSTR(C2,SUBSTR(pos2,-2)+1)
              ELSE C2
         END C1
      ,C3 C2,C4 C3,C5 C4
      ,o.pr c1pr,c3pr c2pr,c4pr c3pr,c5pr c4pr
      ,DECODE(c1pr,o.pr,pos1,'@')
       ||LPAD(LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c2pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos2,LEVEL*2,2)+LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)) pos1
      ,pos3 pos2,pos4 pos3,pos5 pos4
FROM d5,o
UNION
SELECT C1,
       CASE WHEN c2pr<o.pr THEN '('||C2||')' ELSE C2 END
       ||o.op
       ||CASE WHEN c3pr<o.pr THEN '('||C3||')'
              WHEN c3pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C3,DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos3,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c3,SUBSTR(pos3,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)
                   ||SUBSTR(C3,SUBSTR(pos3,-2)+1)
              ELSE C3
         END C2
      ,C4 C3,C5 C4
      ,c1pr,o.pr c2pr,c4pr c3pr,c5pr c4pr
      ,pos1
      ,DECODE(c2pr,o.pr,pos2,'@')
       ||LPAD(LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c3pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos3,LEVEL*2,2)+LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)) pos2
      ,pos4 pos3,pos5 pos4
FROM d5,o
UNION
SELECT C1,C2,
       CASE WHEN c3pr<o.pr THEN '('||C3||')' ELSE C3 END
       ||o.op
       ||CASE WHEN c4pr<o.pr THEN '('||C4||')'
              WHEN c4pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C4,DECODE(LEVEL,1,0,SUBSTR(pos4,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos4,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos4,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c4,SUBSTR(pos4,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos4)/2)
                   ||SUBSTR(C4,SUBSTR(pos4,-2)+1)
              ELSE C4
         END C3
      ,C5 C4
      ,c1pr,c2pr,o.pr c3pr,c5pr c4pr
      ,pos1,pos2
      ,DECODE(c3pr,o.pr,pos3,'@')
       ||LPAD(LENGTH(C3)+1+CASE WHEN c3pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c4pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos4,LEVEL*2,2)+LENGTH(C3)+1+CASE WHEN c3pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos4)/2)) pos3
      ,pos5 pos4
FROM d5,o
UNION
SELECT C1,C2,C3,
       CASE WHEN c4pr<o.pr THEN '('||C4||')' ELSE C4 END
       ||o.op
       ||CASE WHEN c5pr<o.pr THEN '('||C5||')'
              WHEN c5pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C5,DECODE(LEVEL,1,0,SUBSTR(pos5,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos5,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos5,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c5,SUBSTR(pos5,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos5)/2)
                   ||SUBSTR(C5,SUBSTR(pos5,-2)+1)
              ELSE C5
         END C4
      ,c1pr,c2pr,c3pr,o.pr c4pr
      ,pos1,pos2,pos3
      ,DECODE(c4pr,o.pr,pos4,'@')
       ||LPAD(LENGTH(C4)+1+CASE WHEN c4pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c5pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos5,LEVEL*2,2)+LENGTH(C4)+1+CASE WHEN c4pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos5)/2)) pos4
FROM d5,o
)
,d3 AS (
SELECT CASE WHEN c1pr<o.pr THEN '('||C1||')' ELSE C1 END
       ||o.op
       ||CASE WHEN c2pr<o.pr THEN '('||C2||')'
              WHEN c2pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C2,DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos2,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c2,SUBSTR(pos2,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)
                   ||SUBSTR(C2,SUBSTR(pos2,-2)+1)
              ELSE C2
         END C1
      ,C3 C2,C4 C3
      ,o.pr c1pr,c3pr c2pr,c4pr c3pr
      ,DECODE(c1pr,o.pr,pos1,'@')
       ||LPAD(LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c2pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos2,LEVEL*2,2)+LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)) pos1
      ,pos3 pos2,pos4 pos3
FROM d4,o
UNION
SELECT C1,
       CASE WHEN c2pr<o.pr THEN '('||C2||')' ELSE C2 END
       ||o.op
       ||CASE WHEN c3pr<o.pr THEN '('||C3||')'
              WHEN c3pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C3,DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos3,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c3,SUBSTR(pos3,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)
                   ||SUBSTR(C3,SUBSTR(pos3,-2)+1)
              ELSE C3
         END C2
      ,C4 C3
      ,c1pr,o.pr c2pr,c4pr c3pr
      ,pos1
      ,DECODE(c2pr,o.pr,pos2,'@')
       ||LPAD(LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c3pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos3,LEVEL*2,2)+LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)) pos2
      ,pos4 pos3
FROM d4,o
UNION
SELECT C1,C2,
       CASE WHEN c3pr<o.pr THEN '('||C3||')' ELSE C3 END
       ||o.op
       ||CASE WHEN c4pr<o.pr THEN '('||C4||')'
              WHEN c4pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C4,DECODE(LEVEL,1,0,SUBSTR(pos4,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos4,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos4,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c4,SUBSTR(pos4,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos4)/2)
                   ||SUBSTR(C4,SUBSTR(pos4,-2)+1)
              ELSE C4
         END C3
      ,c1pr,c2pr,o.pr c3pr
      ,pos1,pos2
      ,DECODE(c3pr,o.pr,pos3,'@')
       ||LPAD(LENGTH(C3)+1+CASE WHEN c3pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c4pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos4,LEVEL*2,2)+LENGTH(C3)+1+CASE WHEN c3pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos4)/2)) pos3
FROM d4,o
)
,d2 AS (
SELECT CASE WHEN c1pr<o.pr THEN '('||C1||')' ELSE C1 END
       ||o.op
       ||CASE WHEN c2pr<o.pr THEN '('||C2||')'
              WHEN c2pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C2,DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos2,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c2,SUBSTR(pos2,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)
                   ||SUBSTR(C2,SUBSTR(pos2,-2)+1)
              ELSE C2
         END C1
      ,C3 C2
      ,o.pr c1pr,c3pr c2pr
      ,DECODE(c1pr,o.pr,pos1,'@')
       ||LPAD(LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c2pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos2,LEVEL*2,2)+LENGTH(C1)+1+CASE WHEN c1pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)) pos1
      ,pos3 pos2
FROM d3,o
UNION
SELECT C1,
       CASE WHEN c2pr<o.pr THEN '('||C2||')' ELSE C2 END
       ||o.op
       ||CASE WHEN c3pr<o.pr THEN '('||C3||')'
              WHEN c3pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C3,DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos3,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos3,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c3,SUBSTR(pos3,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)
                   ||SUBSTR(C3,SUBSTR(pos3,-2)+1)
              ELSE C3
         END C2
      ,c1pr,o.pr c2pr
      ,pos1
      ,DECODE(c2pr,o.pr,pos2,'@')
       ||LPAD(LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)
       ||DECODE(c3pr,o.pr,(SELECT LISTAGG(LPAD(SUBSTR(pos3,LEVEL*2,2)+LENGTH(C2)+1+CASE WHEN c2pr<o.pr THEN 2 ELSE 0 END,2)) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos3)/2)) pos2
FROM d3,o
)
SELECT DISTINCT
       CASE WHEN c1pr<o.pr THEN '('||C1||')' ELSE C1 END
       ||o.op
       ||CASE WHEN c2pr<o.pr THEN '('||C2||')'
              WHEN c2pr=o.pr AND o.op IN ('-','/') THEN
                   (SELECT LISTAGG(SUBSTR(C2,DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))+1
                                            ,SUBSTR(pos2,LEVEL*2,2) - DECODE(LEVEL,1,0,SUBSTR(pos2,LEVEL*2-2,2))-1
                                          )
                                   ||TRANSLATE(SUBSTR(c2,SUBSTR(pos2,LEVEL*2,2),1),'+-*/','-+/*')
                                   ) WITHIN GROUP(ORDER BY LEVEL) FROM DUAL CONNECT BY LEVEL<LENGTH(pos2)/2)
                   ||SUBSTR(C2,SUBSTR(pos2,-2)+1)
              ELSE C2
         END C1
FROM d2,o;