472,993 Members | 3,190 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,993 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 1613
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
by: Francis Avila | last post by:
A little annoyed one day that I couldn't use the statefulness of generators as "resumable functions", I came across Hettinger's PEP 288 (http://www.python.org/peps/pep-0288.html, still listed as...
10
by: Steve Goldman | last post by:
Hi, I am trying to come up with a way to develop all n-length permutations of a given list of values. The short function below seems to work, but I can't help thinking there's a better way. ...
4
by: Bernard A. | last post by:
hello, i'm looking for a way to have all possible length fixed n-uples from a list, i think generators can help, but was not able to do it myself, maybe some one could point me out to an idea to...
20
by: John Trunek | last post by:
I have a set of X items, but want permutations of length Y (X > Y). I am aware of the permutation functions in <algorithm>, but I don't believe this will do what I want. Is there a way, either...
20
by: anurag | last post by:
hey can anyone help me in writing a code in c (function) that prints all permutations of a string.please help
1
by: JosAH | last post by:
Greetings, last week we talked a bit about generating permutations and I told you that this week will be about combinations. Not true; there's a bit more to tell about permutations and that's...
5
by: Shraddha | last post by:
Suppose we are having 3 variables...a,b,c And we want to print the permutations of these variables...Such as...abc,acb,bca...all 6 of them... But we are not supposed to do it mannually... I...
82
by: Bill Cunningham | last post by:
I don't know if I'll need pointers for this or not. I wants numbers 10^16. Like a credit card 16 digits of possible 10 numbers, so I guess that would be 10^16. So I have int num ; These are of...
2
by: alemo91 | last post by:
Write a recursive function to print all possible permutations of a given string. For example if the input string is “abc” then the set of permutations is: abc, acb, bac, bca, cab, cba. Hint:...
0
by: lllomh | last post by:
Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{
0
tracyyun
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
2
by: giovanniandrean | last post by:
The energy model is structured as follows and uses excel sheets to give input data: 1-Utility.py contains all the functions needed to calculate the variables and other minor things (mentions...
3
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 1 Nov 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM) Please note that the UK and Europe revert to winter time on...
3
by: nia12 | last post by:
Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of...
0
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
4
by: GKJR | last post by:
Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...
3
SueHopson
by: SueHopson | last post by:
Hi All, I'm trying to create a single code (run off a button that calls the Private Sub) for our parts list report that will allow the user to filter by either/both PartVendor and PartType. On...

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.