471,356 Members | 1,676 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,356 software developers and data experts.

Permutations with generators

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?

Thanks in advance,
Pablo

Jul 21 '07 #1
5 1547
Just a quick P.S: This WOULD NOT work with strings, because of
seq.insert()
In very other aspect, I'm still lost.

Jul 21 '07 #2
On Jul 21, 12:42 am, Pablo Torres <tn.pa...@gmail.comwrote:
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
Jul 21 '07 #3
Pablo Torres <tn******@gmail.comwrites:
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])
It's easiest to avoid these mutating schemes and instead just generate
each permutation separately.

def perm(seq):
if len(seq) == 0:
yield []
for (i,s) in enumerate(seq):
for p in perm(seq[:i]+seq[i+1:]):
yield [s]+p
Jul 21 '07 #4
>
list.insert returns None. Thus, except in the one-element case, your
generator is yielding None all the time.
Oh god...silly me.
Thank you guys for the help :)

P.S I'm dead stubborn, so here's what I did to fix my code:

def perm(seq):
"Reshuffles the elements of seq in every possible way"
if len(seq) == 1:
yield seq
else:
for i in range(len(seq)):
for p in perm(seq[1:]):
# Here:
p.insert(i, seq[0])
yield p
Jul 21 '07 #5
Pablo Torres wrote:
AttributeError: 'NoneType' object has no attribute 'insert'

Could somebody please explain to me why my p variable has no type
at all?
It does have a type, NoneType. As already explained, only None
normally is of type NoneType.

Regards,
Björn

--
BOFH excuse #281:

The co-locator cannot verify the frame-relay gateway to the ISDN
server.

Jul 21 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

10 posts views Thread by Steve Goldman | last post: by
4 posts views Thread by Bernard A. | last post: by
20 posts views Thread by John Trunek | last post: by
20 posts views Thread by anurag | last post: by
1 post views Thread by JosAH | last post: by
5 posts views Thread by Shraddha | last post: by
82 posts views Thread by Bill Cunningham | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.