Permutation Generator

[Michael J. Fromberger]

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

-- 
Michael J. Fromberger             | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/  | Dartmouth College, Hanover, NH, USA