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 5 1630
Just a quick P.S: This WOULD NOT work with strings, because of
seq.insert()
In very other aspect, I'm still lost.
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
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
>
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
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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...
|
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. ...
|
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...
|
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...
|
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
|
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...
|
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...
|
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...
|
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:...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |