Puzzleup 2010 比赛快开始了，大家用SQL解答啊

〇〇

with t as(select a m,substr(a,1,1)+0 a,substr(a,2,1)+0 b,substr(a,3,1)+0 c
from (select to_char(level-1,'fm999') a from dual connect by level<=1000)
where substr(a,1,1)not in(substr(a,2,1) ,substr(a,3,1))
and substr(a,2,1)<>substr(a,3,1)
and substr(a,1,1)-substr(a,2,1) not in(-1,1)
and substr(a,3,1)-substr(a,2,1) not in(-1,1)
)
,t2 as(select /*+rule*/a.m||b.m||c.m p
,REPLACE(a.m,GREATEST(a.a,a.b,a.c))m1
       ,REPLACE(b.a,GREATEST(b.a,b.b,b.c))m2
       ,REPLACE(c.a,GREATEST(c.a,c.b,c.c)) m3
from t a,t b, t c
where a.m not in(b.m,c.m) and b.m<>c.m
and length(translate('$1234567890','$'||b.m||a.m,'$'))=5
and length(translate('$1234567890','$'||b.m||c.m,'$'))=5
and length(translate('$1234567890','$'||c.m||a.m,'$'))=5
and length(translate('$1234567890','$'||a.m||b.m||c.m,'$'))=2
and a.a-b.a not in (-1,1)
and c.a-b.a not in (-1,1)
and a.b-b.b not in (-1,1)
and c.b-b.b not in (-1,1)
and a.c-b.c not in (-1,1)
and c.c-b.c not in (-1,1)
)
select * from (select p, m1*m2*m3 m from t2 order by 2 desc)where rownum=1;
P                     M
------------ ----------
637809425        211680

已用时间:  00: 00: 19.12

〇〇

利用对称
第3行和第1行互换不影响
SQL> WITH
  2  n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
  3  select * from(
  4  SELECT path ,m1*m2*m3 m FROM (
  5  SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
  6        ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))m1
  7         ,REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))m2
  8         ,REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m3
  9    FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
10  WHERE n1.n>n7.n and n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
11         AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
12         AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
13         AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
14         AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
15         AND n6.n NOT IN (n7.n,n8.n,n9.n)
16         AND n7.n NOT IN (n8.n,n9.n)
17         AND n8.n<>n9.n
18         AND n1.n NOT IN (n2.n+1,n2.n-1) AND n2.n NOT IN (n3.n+1,n3.n-1)
19         AND n4.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n6.n+1,n6.n-1)
20         AND n7.n NOT IN (n8.n+1,n8.n-1) AND n8.n NOT IN (n9.n+1,n9.n-1)
21         AND n1.n NOT IN (n4.n+1,n4.n-1) AND n4.n NOT IN (n7.n+1,n7.n-1)
22         AND n2.n NOT IN (n5.n+1,n5.n-1) AND n5.n NOT IN (n8.n+1,n8.n-1)
23         AND n3.n NOT IN (n6.n+1,n6.n-1) AND n6.n NOT IN (n9.n+1,n9.n-1)
24  )
25  ORDER BY 2 DESC)
26  WHERE ROWNUM=1;

PATH
-----------------------------------------------------------------------------------------------------
         M
----------
637809425
    211680


已用时间:  00: 00: 03.12

newkid

加上 n1.n>n7.n 确实快了一半。
我不觉得ABS会比NOT IN快，函数调用再怎么说也有开销的吧？

lastwinner

是啊，回头做个测试看看吧，估计是差不了太多
〇〇写的 not in(1, -1)，这个比较好看，而且效率肯定比你的高，呵呵
〇〇的只用在not in外面计算一次加法，而你的需要在not in里面计算两次加法 （减法相当于加个负数）


话说，如果加上9和8在一行
7和6在一行
5和4在一行
的限制条件，速度会不会发生翻天覆地的变化呢？

newkid

其他两种和我的写法差不多：
WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
SELECT * FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
      ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))
       *REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))
       *REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n1.n<n7.n
       AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
       AND n6.n NOT IN (n7.n,n8.n,n9.n)
       AND n7.n NOT IN (n8.n,n9.n)
       AND n8.n<>n9.n
       AND n1.n-n2.n NOT IN (1,-1) AND n2.n-n3.n NOT IN (1,-1)
       AND n4.n-n5.n NOT IN (1,-1) AND n5.n-n6.n NOT IN (1,-1)
       AND n7.n-n8.n NOT IN (1,-1) AND n8.n-n9.n NOT IN (1,-1)
       AND n1.n-n4.n NOT IN (1,-1) AND n4.n-n7.n NOT IN (1,-1)
       AND n2.n-n5.n NOT IN (1,-1) AND n5.n-n8.n NOT IN (1,-1)
       AND n3.n-n6.n NOT IN (1,-1) AND n6.n-n9.n NOT IN (1,-1)
ORDER BY 2 DESC
)
WHERE ROWNUM=1;


WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
SELECT * FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
      ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))
       *REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))
       *REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n1.n<n7.n
       AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
       AND n6.n NOT IN (n7.n,n8.n,n9.n)
       AND n7.n NOT IN (n8.n,n9.n)
       AND n8.n<>n9.n
       AND ABS(n1.n-n2.n)<>1 AND ABS(n2.n-n3.n)<>1
       AND ABS(n4.n-n5.n)<>1 AND ABS(n5.n-n6.n)<>1
       AND ABS(n7.n-n8.n)<>1 AND ABS(n8.n-n9.n)<>1
       AND ABS(n1.n-n4.n)<>1 AND ABS(n4.n-n7.n)<>1
       AND ABS(n2.n-n5.n)<>1 AND ABS(n5.n-n8.n)<>1
       AND ABS(n3.n-n6.n)<>1 AND ABS(n6.n-n9.n)<>1
ORDER BY 2 DESC
)
WHERE ROWNUM=1;


反复运行三个写法，用时都在 1.69 ~ 1.76 波动。

加上你的肉：

WITH
n AS (SELECT ROWNUM-1 n FROM DUAL CONNECT BY ROWNUM<=10)
SELECT * FROM (
SELECT n1.n||n2.n||n3.n||n4.n||n5.n||n6.n||n7.n||n8.n||n9.n path
      ,REPLACE(n1.n||n2.n||n3.n,GREATEST(n1.n,n2.n,n3.n))
       *REPLACE(n4.n||n5.n||n6.n,GREATEST(n4.n,n5.n,n6.n))
       *REPLACE(n7.n||n8.n||n9.n,GREATEST(n7.n,n8.n,n9.n)) m
  FROM n n1,n n2,n n3,n n4,n n5,n n6,n n7,n n8,n n9
WHERE n1.n NOT IN (n2.n,n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n1.n<n7.n
       AND n2.n NOT IN (n3.n,n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n3.n NOT IN (n4.n,n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n4.n NOT IN (n5.n,n6.n,n7.n,n8.n,n9.n)
       AND n5.n NOT IN (n6.n,n7.n,n8.n,n9.n)
       AND n6.n NOT IN (n7.n,n8.n,n9.n)
       AND n7.n NOT IN (n8.n,n9.n)
       AND n8.n<>n9.n
       AND n1.n-n2.n NOT IN (1,-1) AND n2.n-n3.n NOT IN (1,-1)
       AND n4.n-n5.n NOT IN (1,-1) AND n5.n-n6.n NOT IN (1,-1)
       AND n7.n-n8.n NOT IN (1,-1) AND n8.n-n9.n NOT IN (1,-1)
       AND n1.n-n4.n NOT IN (1,-1) AND n4.n-n7.n NOT IN (1,-1)
       AND n2.n-n5.n NOT IN (1,-1) AND n5.n-n8.n NOT IN (1,-1)
       AND n3.n-n6.n NOT IN (1,-1) AND n6.n-n9.n NOT IN (1,-1)
       AND (n1.n,n3.n) IN ((4,5),(5,4),(6,7),(7,6))
       AND (n4.n,n6.n) IN ((4,5),(5,4),(6,7),(7,6),(8,9),(9,8))
       AND (n7.n,n9.n) IN ((6,7),(7,6),(8,9),(9,8))
ORDER BY 2 DESC
)
WHERE ROWNUM=1;

Elapsed: 00:00:00.01

〇〇

用相等条件剪枝简直神了,但理论根据?

〇〇

8X9 明显比 9X8好
前者最小80，后者最多68

〇〇

No: 10       September 15, 2010  

Generating 4-Letter Codes


You will create a list of 4-letter codes using the 26 letters in the English alphabet. The list should not include any code that can be obtained by reversing the order of 2, 3 or 4 adjoining letters of another code in the list.

For example, if the list includes ABCC, then it can't include codes BACC, ACBC, CBAC, ACCB and CCBA.

At most how many codes can be in this list?

〇〇

暴力法
求出所有，挨个删除

newkid

排列组合是SQL的强项。等会有空来写一个。

先分析一下：
不同的组合肯定是互斥的。比如例子用的A,B,C, 它组合的集合和A,B,D肯定是互斥的。
这样的话，只要观察一组，然后乘以 C(3,26)就可以了。同理可适用1,2,4个字母的组合。