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

newkid

第10题：四位编码

利用26个英文字母组成四位编码，在这些编码构成的集合中，一个编码和另一编码不能够存在这样的关系：第一个编码任意取出2,3,4位连续的字串变为反序，构成第二个编码。
例如，假设集合中包含编码ABCC, 则该集合中不能包含下列编码：

BACC  -- 1,2位反序
ACBC  -- 2,3位反序
CBAC  -- 1,2,3位反序
ACCB  -- 2,3,4位反序
CCBA  -- 1,2,3,4位反序

这样的集合，最多可以包含几个编码？

VAR NUM NUMBER;
EXEC :NUM :=2;

WITH c AS (  ---- 求出所有NUM个不同字符构成的四位编码
     SELECT n,POWER(2,ROWNUM) id --- 每个编码占二进制的1位构成ID
       FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') n
               FROM (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=:NUM)
              WHERE LEVEL=4
              CONNECT BY LEVEL<=4
             )
     WHERE TRANSLATE(SUBSTR('1234',1,:NUM),'$'||n,'$') IS NULL  ----- 四位编码中有NUM个不同字符
    )
,s AS ( ----求出所有发生冲突的编码
SELECT t1.id,SUM(t2.id) rev_bits  ---- 这些都是不能出现的id, 每个占一位，按照二进制的位求和就得到所有发生冲突的id的一个总集合
  FROM c t1,c t2
WHERE t2.n IN (t1.n
                --- 两位反序
               ,SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,2)     -- 2134
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,4,1)     -- 1324
               ,SUBSTR(t1.n,1,2)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)     -- 1243
                --- 三位反序
               ,SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)     -- 3214
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)     -- 1432
                --- 四位反序
               ,SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)     -- 4321
               )
GROUP BY t1.id
)
,t(id,cnt,bits) AS ( ---- 递归求出所有不冲突的编码的集合
   SELECT id,1,id FROM s
   UNION ALL
   SELECT s.id,t.cnt+1,t.bits+s.id
     FROM t,s
    WHERE t.id<s.id AND BITAND(t.bits,s.rev_bits)=0  ---- 和所有ID都没有冲突
)
SELECT MAX(cnt) FROM t   ---- 该集合最大可能为多少个元素
;

  MAX(CNT)
----------
         4


jsu@JSU> EXEC :NUM :=3;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.00
jsu@JSU> /

  MAX(CNT)
----------
        15

Elapsed: 00:00:20.20

jsu@JSU> EXEC :NUM :=4;

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.00
jsu@JSU> /

  MAX(CNT)
----------
         8

Elapsed: 00:00:00.11


1*26 + 4*C(2,26) + 15*C(3,26) + 8*C(4,26) = 159926

〇〇

写得比我看得还快...

dingjun123

太高深了，看的脑子晕晕的

newkid

写得匆忙也不知道有没有错。

下面是求出2,3,4个字母的最大集合的一个样本：

AABA,AABB,BABA,BBAB

AACB,ABAC,ABCC,ACBA,ACBB,BACA,BACB,BBAC,BCAC,BCBA,CABC,CBAA,CBAB,CBCA,CCAB

ABDC,ADCB,BCAD,BDCA,CABD,CBDA,DABC,DCAB

newkid

合成一个SQL: (最后的求和没有做)
WITH c AS (  ---- 求出所有NUM个不同字符构成的四位编码
   SELECT num,n,POWER(2,ROW_NUMBER() OVER(PARTITION BY num ORDER BY n)) id
     FROM (SELECT 4-NVL(LENGTH(TRANSLATE('ABCD','$'||n,'$')),0) num,n
             FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') n
                     FROM (SELECT CHR(64+ROWNUM) n FROM DUAL CONNECT BY ROWNUM<=4)
                    WHERE LEVEL=4
                    CONNECT BY LEVEL<=4
                   )
           )
     WHERE TRANSLATE(n,'$'||SUBSTR('ABCD',1,num),'$') IS NULL
    )
,s AS ( ----求出所有发生冲突的编码
SELECT t1.num,t1.id,t1.n,SUM(t2.id) rev_bits  ---- 这些都是不能出现的id, 每个占一位，按照二进制的位求和就得到所有发生冲突的id的一个总集合
  FROM c t1,c t2
WHERE t1.num=t2.num AND
       t2.n IN (t1.n
                --- 两位反序
               ,SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,2)     -- 2134
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,4,1)     -- 1324
               ,SUBSTR(t1.n,1,2)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)     -- 1243
                --- 三位反序
               ,SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)     -- 3214
               ,SUBSTR(t1.n,1,1)||SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)     -- 1432
                --- 四位反序
               ,SUBSTR(t1.n,4,1)||SUBSTR(t1.n,3,1)||SUBSTR(t1.n,2,1)||SUBSTR(t1.n,1,1)     -- 4321
               )
GROUP BY t1.num,t1.id,t1.n
)
,t(num,id,cnt,bits,path) AS ( ---- 递归求出所有不冲突的编码的集合
   SELECT num,id,1,id,n FROM s
   UNION ALL
   SELECT t.num,s.id,t.cnt+1,t.bits+s.id,t.path||','||s.n
     FROM t,s
    WHERE t.num=s.num AND t.id<s.id AND BITAND(t.bits,s.rev_bits)=0  ---- 和所有ID都没有冲突
)
SELECT cnt,path FROM (SELECT t.*,ROW_NUMBER() OVER(PARTITION BY num ORDER BY cnt DESC) rn FROM t)
WHERE rn=1
;


       CNT    PATH
----------  -----------------------------------------------------------------------------------
         1    AAAA
         4    ABBA,ABBB,BAAA,BAAB
        15    AACB,ABAC,ABCB,ABCC,ACBA,BABC,BACA,BBCA,BCAB,BCAC,CABB,CABC,CBAA,CBCA,CCAB
         8    ACBD,ADCB,BADC,BDCA,CADB,CBAD,DBAC,DCBA


Elapsed: 00:00:24.17

lastwinner

我考虑到一种情况，不知对否
假设有一编码c0，按规则翻转后得到集合gc0，gc0中包含c1,c2和其他一些翻转结果，c1不能按规则翻转得到c2
c1和c2分别按规则翻转后得到集合gc1和gc2，gc1和gc2中肯定都包含c0，并且还会包含一些相同的编码，当然剩下的就是不同的编码了

比如c0＝ABCC
c1＝BACC  -- 1,2位反序
c2＝CCBA  -- 1,2,3,4位反序


这时候保留c0，就不如保留c1、c2

——————————————————————————————————————

当然，以上是就个体而言，如果从整体来看，可能选谁都能得到最大的编码数

haiersknl

4个字母序列，非为4类：
有2个字母重复，有3个字母重复，4个字母一样，4个字母都不同。

只研究这四类（然后再乘组合数就OK）：
AABC
AAAB
AAAA
ABCD

我看到你不是这样分类的，这样分类人肉即可，只是ABCD四个字母都不同的时候，人肉会费力，需要程序，你算出了8.

haiersknl

我和你的分类方法不一样，如147楼。算出的值是159276

haiersknl

有两个字母重复的，我是用AABC，楼算AABB，这样人肉后也是159926

newkid

原帖由 haiersknl 于 2010-9-16 14:05 发表
我和你的分类方法不一样，如147楼。算出的值是159276

我的分类方法和你147楼完全等价啊？你到达认为哪个结果是对的？159276是怎么算出来的？