Just satisfied my curiosity wrt this problem, so I might as well share :-) >>> def permute(list): ... if len(list) <= 1: ... yield list ... else: ... for i in xrange(0,len(list)): ... for tail in permute( list[:i] + list[i+1:] ): ... yield [ list[i] ] + tail ... >>> for o in permute([1,2,3]): ... print o ... [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
regards Matt On Fri, 12 Aug 2005 20:48:38 +0100, Michael J. Fromberger <[EMAIL PROTECTED]> wrote: > In article <[EMAIL PROTECTED]>, > Talin <[EMAIL PROTECTED]> wrote: > >> I'm sure I am not the first person to do this, but I wanted to share >> this: a generator which returns all permutations of a list: >> >> def permute( lst ): >> if len( lst ) == 1: >> yield lst >> else: >> head = lst[:1] >> for x in permute( lst[1:] ): >> yield head + x >> yield x + head >> return > > You're right that you're not the first person to do this: Many others > have also posted incorrect permutation generators. > > Have you tried your code on some simple test cases? > > list(permute([1, 2, 3])) > ==> [[1, 2, 3], [2, 3, 1], [1, 3, 2], [3, 2, 1]] > > Notably absent from this list are [2, 1, 3] and [2, 3, 1]. The problem > gets worse with longer lists. The basic problem is that x needs to be > able to occur in ALL positions, not just the beginning and the end. > > Cheers, > -M > -- | Matt Hammond | R&D Engineer, BBC Research and Development, Tadworth, Surrey, UK. -- http://mail.python.org/mailman/listinfo/python-list