在C++的list里面看到的，喜欢研究算法的同学可以玩玩看，呵呵

[转贴]google的top coder的850分题例

假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前
m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5
个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：

如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。

这规则甚是简单，不过有个问题就是同一个 AB
序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的
AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。

如果结果大于10亿就返回-1。

大家不妨当个消遣看看，挺有意思的。既有递归的做法，也有递推的做法。

解决问题的过程远比问题的答案本身更有意思。

下面是我的代码：

def _morph(l) :
    result = []
    for i in range(len(l)) :
        result.append(sum(l[:i+1]))
    return result

def A(lNums) :
    result = _morph(lNums)
    result.insert(0,0)
    return result

def B(lNums) :
    lNums.reverse()
    result = _morph(lNums)
    result.reverse()
    result.append(0)
    return result

def ProbEnumList(s) :
    s = s.upper()
    if s == 'A' :
        return [0, 1]
    elif s == 'B' :
        return [1, 0]
    else :
        previous = ProbEnumList(s[:-1])
        flag = s[-1]
        if flag == 'A' :
            result = A(previous)
        else :
            assert flag == 'B'
            result = B(previous)
        return result

def GetNumOfString(CharacterString) :
    return sum(ProbEnumList(CharacterString))

def GetDescString(s) :
    idxList = [ s.index(c) for c in string.lowercase if c in s ]
    cmpList = zip(idxList[:-1], idxList[1:])
    def AB(ahead, behind) :
        if ahead > behind :
            return 'B'
        else :
            return 'A'
    descList = [ AB(ahead, behind) for ahead, behind in cmpList ]
    return ''.join(descList)

if __name__ == "__main__" :
    import string
    from CombinationEnumerator import PermutationEnumerator

    CHARACTER_STRING = 'ABABAB'

    charNumbers = len(CHARACTER_STRING)
    charList  = list(string.lowercase[:charNumbers+1])

    enum = PermutationEnumerator(charList)
    count = 0
    for i in enum :
        s = ''.join(i)
        descString = GetDescString(s)
        if descString == CHARACTER_STRING :
            count += 1

    print count == GetNumOfString(CHARACTER_STRING)

这里的PermutationEnumerator是我以前写的一个对象，是枚举排列用的，代码可以到cookbook上去查，这里做验证用。

我觉得这种题目，自己想出来远比听别人分析要有意思。这种想了半天没一点思路，突然柳暗花明，茅塞顿开的感觉真是是很妙。希望大家也能享受到这种感觉。


On 3/17/06, 马踏飞燕 <honeyday.mj at gmail.com> wrote:
> 在C++的list里面看到的，喜欢研究算法的同学可以玩玩看，呵呵
>
> [转贴]google的top coder的850分题例
>
> 假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前
> m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5
> 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
>
> 现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：
>
> 如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
> 如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
> 如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。
>
> 这规则甚是简单，不过有个问题就是同一个 AB
> 序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的
> AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
>
> 如果结果大于10亿就返回-1。
>
> 大家不妨当个消遣看看，挺有意思的。既有递归的做法，也有递推的做法。
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>

在 06-3-21，shhgs<shhgs.efhilt at gmail.com> 写道：
> 解决问题的过程远比问题的答案本身更有意思。
>
> 下面是我的代码：
>
> def _morph(l) :
>    result = []
>    for i in range(len(l)) :
>        result.append(sum(l[:i+1]))
>    return result
>
> def A(lNums) :
>    result = _morph(lNums)
>    result.insert(0,0)
>    return result
>
> def B(lNums) :
>    lNums.reverse()
>    result = _morph(lNums)
>    result.reverse()
>    result.append(0)
>    return result
>
> def ProbEnumList(s) :
>    s = s.upper()
>    if s == 'A' :
>        return [0, 1]
>    elif s == 'B' :
>        return [1, 0]
>    else :
>        previous = ProbEnumList(s[:-1])
>        flag = s[-1]
>        if flag == 'A' :
>            result = A(previous)
>        else :
>            assert flag == 'B'
>            result = B(previous)
>        return result
>
> def GetNumOfString(CharacterString) :
>    return sum(ProbEnumList(CharacterString))
>
> def GetDescString(s) :
>    idxList = [ s.index(c) for c in string.lowercase if c in s ]
>    cmpList = zip(idxList[:-1], idxList[1:])
>    def AB(ahead, behind) :
>        if ahead > behind :
>            return 'B'
>        else :
>            return 'A'
>    descList = [ AB(ahead, behind) for ahead, behind in cmpList ]
>    return ''.join(descList)
>
> if __name__ == "__main__" :
>    import string
>    from CombinationEnumerator import PermutationEnumerator
>
>    CHARACTER_STRING = 'ABABAB'
>
>    charNumbers = len(CHARACTER_STRING)
>    charList  = list(string.lowercase[:charNumbers+1])
>
>    enum = PermutationEnumerator(charList)
>    count = 0
>    for i in enum :
>        s = ''.join(i)
>        descString = GetDescString(s)
>        if descString == CHARACTER_STRING :
>            count += 1
>
>    print count == GetNumOfString(CHARACTER_STRING)
>
> 这里的PermutationEnumerator是我以前写的一个对象，是枚举排列用的，代码可以到cookbook上去查，这里做验证用。
>
> 我觉得这种题目，自己想出来远比听别人分析要有意思。这种想了半天没一点思路，突然柳暗花明，茅塞顿开的感觉真是是很妙。希望大家也能享受到这种感觉。
>
>

哈哈，是的是的。
其实最有成就感的就是那"茅塞顿开"的一刹那！

还有类似的challenge吗？可以用来锻炼锻炼思路。

On 3/21/06, 马踏飞燕 <honeyday.mj at gmail.com> wrote:
> 在 06-3-21，shhgs<shhgs.efhilt at gmail.com> 写道：
> > 解决问题的过程远比问题的答案本身更有意思。
> >
> > 下面是我的代码：
> >
> > def _morph(l) :
> >    result = []
> >    for i in range(len(l)) :
> >        result.append(sum(l[:i+1]))
> >    return result
> >
> > def A(lNums) :
> >    result = _morph(lNums)
> >    result.insert(0,0)
> >    return result
> >
> > def B(lNums) :
> >    lNums.reverse()
> >    result = _morph(lNums)
> >    result.reverse()
> >    result.append(0)
> >    return result
> >
> > def ProbEnumList(s) :
> >    s = s.upper()
> >    if s == 'A' :
> >        return [0, 1]
> >    elif s == 'B' :
> >        return [1, 0]
> >    else :
> >        previous = ProbEnumList(s[:-1])
> >        flag = s[-1]
> >        if flag == 'A' :
> >            result = A(previous)
> >        else :
> >            assert flag == 'B'
> >            result = B(previous)
> >        return result
> >
> > def GetNumOfString(CharacterString) :
> >    return sum(ProbEnumList(CharacterString))
> >
> > def GetDescString(s) :
> >    idxList = [ s.index(c) for c in string.lowercase if c in s ]
> >    cmpList = zip(idxList[:-1], idxList[1:])
> >    def AB(ahead, behind) :
> >        if ahead > behind :
> >            return 'B'
> >        else :
> >            return 'A'
> >    descList = [ AB(ahead, behind) for ahead, behind in cmpList ]
> >    return ''.join(descList)
> >
> > if __name__ == "__main__" :
> >    import string
> >    from CombinationEnumerator import PermutationEnumerator
> >
> >    CHARACTER_STRING = 'ABABAB'
> >
> >    charNumbers = len(CHARACTER_STRING)
> >    charList  = list(string.lowercase[:charNumbers+1])
> >
> >    enum = PermutationEnumerator(charList)
> >    count = 0
> >    for i in enum :
> >        s = ''.join(i)
> >        descString = GetDescString(s)
> >        if descString == CHARACTER_STRING :
> >            count += 1
> >
> >    print count == GetNumOfString(CHARACTER_STRING)
> >
> > 这里的PermutationEnumerator是我以前写的一个对象，是枚举排列用的，代码可以到cookbook上去查，这里做验证用。
> >
> > 我觉得这种题目，自己想出来远比听别人分析要有意思。这种想了半天没一点思路，突然柳暗花明，茅塞顿开的感觉真是是很妙。希望大家也能享受到这种感觉。
> >
> >
>
> 哈哈，是的是的。
> 其实最有成就感的就是那"茅塞顿开"的一刹那！
>
> _______________________________________________
> python-chinese
> Post: send python-chinese at lists.python.cn
> Subscribe: send subscribe to python-chinese-request at lists.python.cn
> Unsubscribe: send unsubscribe to  python-chinese-request at lists.python.cn
> Detail Info: http://python.cn/mailman/listinfo/python-chinese
>
>