PUZZLEUP 2014

peter1166

都已经第四题了， 竟然没看到第三题。

newkid

第三题上周发了。把第四做出来给你章。

peter1166

两个的出来了， 三个的跑不出来了， 想想其他方法。

AABBA        5
BBAAB        5
BAABB        5
ABBAA        5

peter1166

如果所有的四字母组合（从AAAA到DDDD）必须包含在文本中

这个是不是说 ABCD 都包含， 例如， 两个的时候是 AB , BA   不包含 AA , BB  ？ 因为 AA 不是所有两字母组合之一 。
如果是这样的话， 2个字母的情况是 ：
ABA
BAB

3个字母的情况是：
ABCABACBA        9
CBACBCABC        9
CABCACBAC        9
BCABCBACB        9
BACBABCAB        9
ACBACABCA        9

solomon_007

peter1166 发表于 2014-8-21 09:25
两个的出来了， 三个的跑不出来了， 想想其他方法。

AABBA        5

两个的出来了， 三个的跑不出来了,   我的也是这样。。。

对于三个的：长度为14的A,B,C任何组合串中，最大的长度为3的不同的子串为 12

peter1166

solomon_007 发表于 2014-8-21 17:04
两个的出来了， 三个的跑不出来了,   我的也是这样。。。

对于三个的：长度为14的A,B,C任何组合串中， ...

  猫猫跟我卡一个地方了。  你的 【3】14 -12  用了多长时间 ？

peter1166

3 个的其中一个情况出来了， 下面尝试 4个 的。

S                                 L      STR
--------------------------------- ------ -----------------------------------------------------------------------------------------------------------
AAABAACABBABCACBACCBBBCBCCCAA     29     |AAA|AAB|ABA|BAA|AAC|ACA|CAB|ABB|BBA|BAB|ABC|BCA|CAC|ACB|CBA|BAC|ACC|CCB|CBB|BBB|BBC|BCB|CBC|BCC|CCC|CCA|CAA

peter1166

4 个的也出来结果了， 这个算不算做出来。 也能马上出来结果。


SELECT LENGTH(S) L, S ,  STR
FROM (
      SELECT 'AAA'||REPLACE(SYS_CONNECT_BY_PATH(SUBSTR(S,DECODE(LEVEL,0,2,-1)),'|'),'|','') S
             ,SYS_CONNECT_BY_PATH(S,'|') STR
      FROM (
            SELECT REPLACE(SYS_CONNECT_BY_PATH(S,','),',','') S
            FROM (
            SELECT 'A' S FROM DUAL UNION ALL
            SELECT 'B' S FROM DUAL UNION ALL
            SELECT 'C' S FROM DUAL UNION ALL
            SELECT 'D' S FROM DUAL
            )
            WHERE LEVEL = 4
            CONNECT BY  LEVEL <= 4
           )
      WHERE LEVEL = POWER(4,4)
      CONNECT BY NOCYCLE PRIOR SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1) AND PRIOR S <> S
      START WITH S IN ('AAAA')  
     )
WHERE ROWNUM <= 1
/

L    S                                                                                STR
---- -------------------------------------------------------------------------------- --------------------------------------------------------------------------------
259         AAAABAAACAAADAABBAABCAABDAACBAACCAACDAADBAADCAADDABABACABADABBBABBCABBDABCBABCCABCDABDBABDCABDDACACADACBBACBCACBDACCBACCCACCDACDBACDCACDDADADBBADBCADBDADCBADCCADCDADDBADDCADDDBBBBCBBBDBBCCBBCDBBDCBBDDBCBCBDBCCCBCCDBCDCBCDDBDBDCCBDCDBDDCBDDDCCCCDCCDDCDCDDDDAAA        |AAAA|AAAB|AABA|ABAA|BAAA|AAAC|AACA|ACAA|CAAA|AAAD|AADA|ADAA|DAAB|AABB|ABBA|BBAA|BAAB|AABC|ABCA|BCAA|CAAB|AABD|ABDA|BDAA|DAAC|AACB|ACBA|CBAA|BAAC|AACC|ACCA|CCAA|CAAC|AACD|ACDA|CDAA|DAAD|AADB|ADBA|DBAA|BAAD|AADC|ADCA|DCAA|CAAD|AADD|ADDA|DDAB|DABA|ABAB|BABA|ABAC|BACA|ACAB|CABA|ABAD|BADA|ADAB|DABB|ABBB|BBBA|BBAB|BABB|ABBC|BBCA|BCAB|CABB|ABBD|BBDA|BDAB|DABC|ABCB|BCBA|CBAB|BABC|ABCC|BCCA|CCAB|CABC|ABCD|BCDA|CDAB|DABD|ABDB|BDBA|DBAB|BABD|ABDC|BDCA|DCAB|CABD|ABDD|BDDA|DDAC|DACA|ACAC|CACA|ACAD|CADA|ADAC|DACB|ACBB|CBBA|BBAC|BACB|ACBC|CBCA|BCAC|CACB|ACBD|CBDA|BDAC|DACC|ACCB|CCBA|CBAC|BACC|ACCC|CCCA|CCAC|CACC|ACCD|CCDA|CDAC|DACD|ACDB|CDBA|DBAC|BACD|ACDC|CDCA|DCAC|CACD|ACDD|CDDA|DDAD|DADA|ADAD|DADB|ADBB|DBBA|BBAD|BADB|ADBC|DBCA|BCAD|CADB|ADBD|DBDA|BDAD|DADC|ADCB|DCBA|CBAD|BADC|ADCC|DCCA|CCAD|CADC|ADCD|DCDA|CDAD|DADD|ADDB|DDBA|DBAD|BADD|ADDC|DDCA|DCAD|CADD|ADDD|DDDB|DDBB|DBBB|BBBB|BBBC|BBCB|BCBB|CBBB|BBBD|BBDB|BDBB|DBBC|BBCC|BCCB|CCBB|CBBC|BBCD|BCDB|CDBB|DBBD|BBDC|BDCB|DCBB|CBBD|BBDD|BDDB|DDBC|DBCB|BCBC|CBCB|BCBD|CBDB|BDBC|DBCC|BCCC|CCCB|CCBC|CBCC|BCCD|CCDB|CDBC|DBCD|BCDC|CDCB|DCBC|CBCD|BCDD|CDDB|DDBD|DBDB|BDBD|DBDC|BDCC|DCCB|CCBD|CBDC|BDCD|DCDB|CDBD|DBDD|BDDC|DDCB|DCBD|CBDD|BDDD|DDDC|DDCC|DCCC|CCCC|CCCD|CCDC|CDCC|DCCD|CCDD|CDDC|DDCD|DCDC|CDCD|DCDD|CDDD|DDDD|DDDA|DDAA|DAAA

peter1166

newkid 发表于 2014-8-21 07:47
第三题上周发了。把第四做出来给你章。

想要个路虎， 有徽章有动力 。  

newkid

陆虎转给你了！
我从没考虑过CONNECT BY，谁知道它这么给力？由此可推测内部是深度优先的。

我的回溯法代码如下：
DECLARE
  v_str VARCHAR2(300);
  v_n NUMBER :=4;
  v_target NUMBER:= POWER(v_n,v_n)+v_n-1;
  v_try NUMBER :=0;
  v_backtrace BOOLEAN := TRUE;
BEGIN
  v_str := LPAD('1',v_n,'1');
  WHILE LENGTH(v_str)<v_target LOOP
        v_backtrace := TRUE;
        FOR i IN v_try+1 .. v_n LOOP
            IF INSTR(v_str,SUBSTR(v_str,-v_n+1)||i)=0 THEN
               v_backtrace := FALSE;
               v_str := v_str||i;
               EXIT;
            END IF;
        END LOOP;
        IF v_backtrace THEN
           v_try := TO_NUMBER(SUBSTR(v_str,-1));
           v_str := SUBSTR(v_str,1,LENGTH(v_str)-1);
        ELSE
           v_try := 0;
        END IF;
  END LOOP;
  DBMS_OUTPUT.PUT_LINE(TRANSLATE(v_str,'1234','ABCD'));
END;
/