PUZZLEUP 2014

peter1166

newkid 发表于 2014-8-21 21:25
陆虎转给你了！
我从没考虑过CONNECT BY，谁知道它这么给力？由此可推测内部是深度优先的。

已收到，谢谢， newkid 。  期待下一题。   上周休假， 第三题没看到， 抽空也做看看。  

solomon_007

peter1166 发表于 2014-8-21 17:42
猫猫跟我卡一个地方了。  你的 【3】14 -12  用了多长时间 ？

NBA,

昨天研究、【3】的时候，发现：
10 -8
11-9
12-10
13-11
14-12
。。。

后面太费时间了。。。就是没有发现这个规律： SUBSTR(S,2) =  SUBSTR(S,1,LENGTH(S)-1)  

另外，你的SQL里的DECODE可以不要啊：

  SELECT LENGTH(S),S,STR
   FROM (   
  SELECT SYS_CONNECT_BY_PATH(S,'|') STR,
             'AAA'||REPLACE(SYS_CONNECT_BY_PATH(SUBSTR(S,-1),'|'),'|','') S
      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

peter1166

solomon_007 发表于 2014-8-22 09:21
NBA,

昨天研究、【3】的时候，发现：

猫猫， 眼睛犀利。  那个DECODE 本来是想合并字段的时候， 除了第一个外都只要最后一个字符来着。
不成想下面有个  WHERE LEVEL = POWER(4,4) 实现不了。 后来就前面加了  'AAA',  DECODE 忘记去掉了。 谢谢， 猫猫指正。   
后来我想是不是也可以用 WITH 递归也可以实现这个， 这个时候合并字段的时候也许可能更灵活。

jixch

额....陷入自己挖的死胡同了....
还是第四题
扩展的问一下：
如果不确定总字符长度，而且也不确认分个的字符（AAA,AAB）是否需要重复，该如果求解
比如：
以三个字符为例。
只用字母A,B,C创建一个文本。如果所有的三字母组合（从AAA到CCC）必须包含在文本中，最小的文本长度是多少？
不能确认最小字符长度为29， 也不能确认每个三字母组合只会用到一次。
那么该怎么处理

另外，之前好像看到有人说有一个关于 同伙 问题的帖子，各位能不能找到链接。谢谢了。

newkid

jixch 发表于 2014-8-25 18:59
额....陷入自己挖的死胡同了....
还是第四题
扩展的问一下：

这个最小长度是先有理论上的猜测，然后我们找出了实例。如果不加这个限制，也可以在最坏情况下（27*3）去找，组合数就更多，程序可能跑不出来。

找团伙：
http://www.itpub.net/thread-1851315-1-2.html

lastwinner

peter1166 发表于 2014-8-21 20:11
4 个的也出来结果了， 这个算不算做出来。 也能马上出来结果。

我直接想到的也是connect by，先构造出256个4字节字符串（4^4），用4字节字符串的后面三字节和其他的4字节字符串的前三字节匹配为条件去寻找

理论 上来说，结果就最小应该是259，因为256个字符串都不一样，所以每个都要占一个字节，再加上第一个字符串还需要3字节，所以最小就是259字节，但至于是不是就是259字节，需要证明。

只是在一开始觉得不应该从AAAA出发，而应该是个其他的什么字符串，后来想了想，这些字符串都是等价的，从哪个开始都没问题

ps：LEVEL = POWER(4,4) 属于未卜先知了，你怎么知道level为POWER(4,4) 就一定有答案？

lastwinner

newkid 发表于 2014-8-21 21:25
陆虎转给你了！
我从没考虑过CONNECT BY，谁知道它这么给力？由此可推测内部是深度优先的。

是的，是深度优先，在这个帖子里很早就写到了
http://www.itpub.net/forum.php?m ... %3D28%26typeid%3D28

peter1166

lastwinner 发表于 2014-8-26 10:34
我直接想到的也是connect by，先构造出256个4字节字符串（4^4），用4字节字符串的后面三字节和其他的4字节 ...

老师的意识是否是应该这么写？

WITH T AS (
        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
)
SELECT LENGTH(S),S
FROM (   
     SELECT SYS_CONNECT_BY_PATH(S,'|') STR,
            'AAA'||REPLACE(SYS_CONNECT_BY_PATH(SUBSTR(S,-1),'|'),'|','') S
     FROM T
     WHERE LEVEL = (SELECT COUNT(*) FROM T)
     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
/

lastwinner

peter1166 发表于 2014-8-26 13:44
老师的意识是否是应该这么写？

WITH T AS (

不是的，(SELECT COUNT(*) FROM T)也是256
问题在于，你怎么知道256个字符串一定能不重复的首尾相连的串在一起？我的意思是，level至少是256，但也有可能是257,258……

newkid

lastwinner 发表于 2014-8-26 17:13
不是的，(SELECT COUNT(*) FROM T)也是256
问题在于，你怎么知道256个字符串一定能不重复的首尾相连的串 ...

他用了NOCYCLE, 所以LEVEL不可能超过256了。
最后的WHERE LEVEL=POWER(4,4) 是属于“大胆假设小心求证”。
从AAAA出发也是一个大胆假设，并不等价于ABCD。如果是一个首尾衔接的环，那么从哪个出发就是等价的。