Permutaion实现时，当selection = 1时是会报错的。

======= 2006-03-07 08:14:47 您在来信中写道：=======

>Python就是爽
>
>思路出来，代码只是小case，原本以为要调试一番，结果是白担心了
>
>Permutaion用了链表，Combination用来二叉树，不过代码里看不出二叉树。这是设计算法的时候加的辅助线，真正写代码的时候反而用不着了。也挺有意思的。
>
>已经给Python Cookbook发邮件了，希望能收录。
>
>On 3/5/06, Bruce Wang <number5 at gmail.com> wrote:
>> On 3/6/06, shhgs <shhgs.efhilt at gmail.com> wrote:
>> > 我有思路了，过两天等有空了写出来
>> >
>> > 这段代码是不是够资格贴到cookbook？
>> >
>>
>> 够资格了 :)
>>
>> 其实那里没什么限制的
>>
>> --
>> simple is good
>> http://brucewang.net
>>
>> _______________________________________________
>> 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
>>
>>
>_______________________________________________
>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

= = = = = = = = = = = = = = = = = = = =

-------------- next part --------------
A non-text attachment was scrubbed...
Name: wangzhe.vcf
Type: text/x-vcard
Size: 304 bytes
Desc: not available
Url : http://lists.exoweb.net/pipermail/python-chinese/attachments/20060307/ce20c148/wangzhe.vcf

已经更正了代码，贴到cookbook上了，具体的算法分析也给了

下面把代码再帖一遍

def CombinationEnumerator(listObj, selection) :
    class CombEnum(object) :
        def __init__(self, listObj, selection) :
            assert selection <= len(listObj)
            self.items = listObj
            self.route = ([True, ]*selection) + [False,
]*(len(listObj)-selection)
            self.selection = selection
        def value(self) :
            result = [ val for flag, val in zip(self.route,
self.items) if flag ]
            return result
        def next(self) :
            try :
                while self.route[-1] :
                    self.route.pop()
                while not self.route[-1] :
                    self.route.pop()
            except :
                return False

            self.route[-1] = False

            count = self.route.count(True)
            self.route.extend( (self.selection - count) * [True,] )
            padding = len(self.items) - len(self.route)
            self.route.extend( padding * [False, ])
            return True

    if selection == 0 :
        yield []
        return

    rotor = CombEnum(listObj, selection)
    yield rotor.value()
    while rotor.next() :
        yield rotor.value()

def PermutationEnumerator(choice, selection) :
    class Rotor(object) :
        def __init__(self, choice, selection, parent = None) :
            assert len(choice) >= selection
            self.selection = selection
            self.parent = parent
            self.choice = choice
            self.cursor  = 0
            if selection == 1 :
                self.child = None
            else :
                self._spawn_child()
        def value(self) :
            if self.child :
                result = self.child.value()
                result.append(self.choice[self.cursor])
                return result
            else :
                return [ self.choice[self.cursor], ]
        def _spawn_child(self) :
            assert self.selection >= 2
            cursor = self.cursor
            child_choice = self.choice[:cursor] + self.choice[cursor + 1:]
            self.child = Rotor(child_choice, self.selection -1,  self)
        def next(self) :
            result = False
            if self.child :
                result = self.child.next()

            if result :
                return result
            else :
                self.cursor += 1
                if self.cursor == len(self.choice) :
                    return False
                else :
                    if self.child :
                        self._spawn_child()
                    return True

    rotor = Rotor(choice, selection)
    yield rotor.value()
    while rotor.next() :
        yield rotor.value()

if __name__ == "__main__" :
    items = [ 'a', 'b', 'c']
    for algo in (CombinationEnumerator, PermutationEnumerator) :
        for selection in range(1, 4) :
            print algo.__name__
            print items
            print selection
            enum = algo(items, selection)
            for i in enum :
                print i
            print "\n\n\n"


On 3/6/06, wangzhe <wangzhe at eastcom.com> wrote:
> Permutaion实现时，当selection = 1时是会报错的。
>
> ======= 2006-03-07 08:14:47 您在来信中写道：=======
>
> >Python就是爽
> >
> >思路出来，代码只是小case，原本以为要调试一番，结果是白担心了
> >
> >Permutaion用了链表，Combination用来二叉树，不过代码里看不出二叉树。这是设计算法的时候加的辅助线，真正写代码的时候反而用不着了。也挺有意思的。
> >
> >已经给Python Cookbook发邮件了，希望能收录。
> >
> >On 3/5/06, Bruce Wang <number5 at gmail.com> wrote:
> >> On 3/6/06, shhgs <shhgs.efhilt at gmail.com> wrote:
> >> > 我有思路了，过两天等有空了写出来
> >> >
> >> > 这段代码是不是够资格贴到cookbook？
> >> >
> >>
> >> 够资格了 :)
> >>
> >> 其实那里没什么限制的
> >>
> >> --
> >> simple is good
> >> http://brucewang.net
> >>
> >> _______________________________________________
> >> 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
> >>
> >>
> >_______________________________________________
> >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
>
> = = = = = = = = = = = = = = = = = = = =
>
>
> _______________________________________________
> 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
>
>
>