Re: Permutations with generators

On Jul 21, 12:42 am, Pablo Torres <tn.pa...@xxxxxxxxx> 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


.

Relevant Pages

  • Permutations with generators
    ... "Reshuffles the elements of seq in every possible way" ... yield p.insert ... and then I insert seq, the first element of the original sequence, ... File "perm.py", line 11, in perm ...
    (comp.lang.python)
  • Re: global interpreter lock
    ... > I don't see how generators substitute for microthreads. ... I've done some digging and found what you mean by microthreads - ... it's late here) - the operation that would block normally you yield inside ... > yields in different parts of that state machine. ...
    (comp.lang.python)
  • Re: How to identify generator/iterator objects?
    ... generator/iterator that can yield iterators, generators, and other data ... generator and iterator objects. ... So while I can identify iterators, I can't identify generators by class. ... this flattening effect? ...
    (comp.lang.python)
  • Re: How to identify generator/iterator objects?
    ... generator/iterator that can yield iterators, generators, and other data ... So while I can identify iterators, I can't identify generators by class. ... this flattening effect? ...
    (comp.lang.python)
  • Re: Weird generator id() behaviour (was Re: Python code written in1998, how to improve/change it?)
    ... The reason, I think, for the unusual sequence if ids of the generators - see grandparent post -, is because the reference to the generator is being lost, then another generator is being created with the same id. ...
    (comp.lang.python)