Permutation Generator

[Matt Hammond]

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  
<Michael.J.Fromberger at Clothing.Dartmouth.EDU> wrote:

> In article <mailman.3042.1123875574.10512.python-list at python.org>,
>  Talin <talin at acm.org> 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.