Permutations with generators

[Dan Bishop]

On Jul 21, 12:42 am, Pablo Torres <tn.pa... at gmail.com> wrote:
> Hey guys!
> For the last couple of days, I've been fighting a war against
> generators and they've beaten the crap out of me several times. What I
> want to do is implement one that yields every possible permutation of
> a given sequence (I had lists in mind, but I could swear that this
> would work on strings too...if it worked at all).
>
> Here's what I have so far:
>
> def perm(seq):
>         "Reshuffles the elements of seq in every possible way"
>         if len(seq) == 1:
>                 yield seq
>         else:
>                 for p in perm(seq[1:]):
>                         for i in range(len(seq)):
>                                 yield p.insert(i, seq[0])
>
> Basically, I let the recursion reshuffle the elements of the
> subsequence that starts from the second element of the original one,
> and then I insert seq[0], the first element of the original sequence,
> in every position of the shuffled sublist.
>
> Here's what I get when I try to list the permutations of [1, 2, 3, 4]
> (print list(perm([1, 2, 3, 4]))):
>
> Traceback (most recent call last):
>   File "perm.py", line 15, in <module>
>     print list(perm([1, 2, 3, 4]))
>   File "perm.py", line 11, in perm
>     for p in perm(seq[1:]):
>   File "perm.py", line 13, in perm
>     yield p.insert(i, seq[0])
> AttributeError: 'NoneType' object has no attribute 'insert'
>
> Could somebody please explain to me why my p variable has no type at
> all?
> For every call to perm(seq), seq should always be of the same type as
> the sequence that was used in the first call. Any ideas as to where
> seq loses it's type?

list.insert returns None.  Thus, except in the one-element case, your
generator is yielding None all the time.

Try this:

def permutations(seq):
    if len(seq) == 1:
        yield seq
    else:
        for i, x in enumerate(seq):
            for perm in permutations(seq[:i] + seq[i+1:]):
                yield [x] + perm