469,579 Members | 1,899 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,579 developers. It's quick & easy.

TypeError, I know why but not how!?

Im looking into PvsNP:
http://www.claymath.org/millennium/P_vs_NP/
so I thought I'd write the program just to get a feel for it.
But I run into a problem. Why does it all the sudden return None? I
mean I know why the program aborts but I dont understand why the None
is generated all the sudden. Hitting recursion depth isn't reported
with that error.
Guess I am missing something very obvious.

Traceback (most recent call last):
File "C:\Python25\Progs\PNP\pnp.py", line 34, in <module>
gen(50)
File "C:\Python25\Progs\PNP\pnp.py", line 32, in gen
return generateList([], [(1,10),(4,272),(34,442),(112,42)], [],
rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 27, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 27, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 27, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 27, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 27, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 25, in generateList
room, placed = pair(incompatibles, placed)
File "C:\Python25\Progs\PNP\pnp.py", line 12, in pair
student1, placed = validate(placed)
TypeError: 'NoneType' object is not iterable
>>>
----------------------------------
the program:

import random

def validate(placed):
student = round(random.random()*401)
if student in placed:
validate(placed)
else:
placed.append(student)
return student, placed

def pair(incompatibles, placed):
student1, placed = validate(placed)
student2, placed = validate(placed)
pair1 = (student1,student2)
pair2 = (student2,student1)
if (pair1 or pair2) in incompatibles:
placed.remove(student1)
placed.remove(student2)
pair(incompatibles, placed)
else:
return pair1, placed

def generateList(dormlist,incompatibles, placed, rooms):
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatibles, placed)
dormlist.append(room)
generateList(dormlist,incompatibles,placed,rooms)
else:
return dormlist

def gen(rooms):
return generateList([], [(1,10),(4,272),(34,442),(112,42)], [],
rooms)

gen(50)
-------------------------------------------------------------------------------------------------------------------
some tests inserted:
import random

def validate(placed):
student = round(random.random()*401)
if student in placed:
validate(placed)
else:
placed.append(student)
return student, placed

def pair(incompatibles, placed):
x = validate(placed)
print "x",x
y = validate(placed)
print "y",y
print "-------------------------------------"
student1, placed = x
student2, placed = y
#student1, placed = validate(placed)
#student2, placed = validate(placed)
pair1 = (student1,student2)
pair2 = (student2,student1)
if (pair1 or pair2) in incompatibles:
placed.remove(student1)
placed.remove(student2)
pair(incompatibles, placed)
else:
return pair1, placed

def generateList(dormlist,incompatibles, placed, rooms):
## print dormlist
## print placed
## print "---------------------------------------------------"
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatibles, placed)
dormlist.append(room)
generateList(dormlist,incompatibles,placed,rooms)
else:
return dormlist

def gen(rooms):
return generateList([], [(1,10),(4,272),(34,442),(112,42)], [],
rooms)

gen(50)

------------------------
x (283.0, [283.0])
y (8.0, [283.0, 8.0])
-------------------------------------
x (359.0, [283.0, 8.0, 359.0])
y (158.0, [283.0, 8.0, 359.0, 158.0])
-------------------------------------
x (249.0, [283.0, 8.0, 359.0, 158.0, 249.0])
y (371.0, [283.0, 8.0, 359.0, 158.0, 249.0, 371.0])
-------------------------------------
x (199.0, [283.0, 8.0, 359.0, 158.0, 249.0, 371.0, 199.0])
y (292.0, [283.0, 8.0, 359.0, 158.0, 249.0, 371.0, 199.0, 292.0])
-------------------------------------
x None
y (227.0, [283.0, 8.0, 359.0, 158.0, 249.0, 371.0, 199.0, 292.0, 47.0,
227.0])
-------------------------------------

Traceback (most recent call last):
File "C:\Python25\Progs\PNP\pnp.py", line 44, in <module>
gen(50)
File "C:\Python25\Progs\PNP\pnp.py", line 42, in gen
return generateList([], [(1,10),(4,272),(34,442),(112,42)], [],
rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 37, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 37, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 37, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 37, in generateList
generateList(dormlist,incompatibles,placed,rooms)
File "C:\Python25\Progs\PNP\pnp.py", line 35, in generateList
room, placed = pair(incompatibles, placed)
File "C:\Python25\Progs\PNP\pnp.py", line 17, in pair
student1, placed = x
TypeError: 'NoneType' object is not iterable
Jul 10 '08 #1
6 1332
ssecorp wrote:
Im looking into PvsNP:
http://www.claymath.org/millennium/P_vs_NP/
so I thought I'd write the program just to get a feel for it.
But I run into a problem. Why does it all the sudden return None? I
mean I know why the program aborts but I dont understand why the None
is generated all the sudden. Hitting recursion depth isn't reported
with that error.
def validate(placed):
student = round(random.random()*401)
if student in placed:
# You need to explicitly return, here:
return validate(placed)
else:
placed.append(student)
return student, placed

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

Jul 10 '08 #2
On 2008-07-10, ssecorp <ci**********@gmail.comwrote:
>
def validate(placed):
student = round(random.random()*401)
if student in placed:
validate(placed)
else:
placed.append(student)
return student, placed

def pair(incompatibles, placed):
student1, placed = validate(placed)
student2, placed = validate(placed)
pair1 = (student1,student2)
pair2 = (student2,student1)
if (pair1 or pair2) in incompatibles:
placed.remove(student1)
placed.remove(student2)
pair(incompatibles, placed)
else:
return pair1, placed

def generateList(dormlist,incompatibles, placed, rooms):
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatibles, placed)
dormlist.append(room)
generateList(dormlist,incompatibles,placed,rooms)
else:
return dormlist
In each of the above functions, the 'if' part has no 'return', while the 'else'
part has. You should add a 'return' statement at every exit from the function.
If you don't expect the program to get at some point, you should add a check
like

raise ValueError("This shouldn't happen")

you'd be surprised how often 'impossible' things do happen (and writing such a
statement costs less than a minute, and saves you many hours debugging).
Some people so as far as demanding that there is exactly 1 return statement,
namely at the bottom of the function. While I don't favor that approach, it may
help you in always returning a value.

BTW: For performance and readability, you may want to replace your direct
recursion with iterations.
Albert
Jul 10 '08 #3
ty I came to the same conckusion in bed :)

now it works.
however since there are 400 students and some are incompatible I
shouldnt be able to generate a 200room list right?

but it works sometimes the other times i get an error. might be
because of recursion depth i never let the error finish.
i saw i also generate student 0 which shouldnt exist.


and the actual problem is generating all possible combinations right?
i mean i can easily generate one list that is made randomly so problem
solved.

why does one need to generate all possible lists? i guess there are
other problems where that might be needed so is this just a bad
example or am i missing something?
Jul 10 '08 #4
On Jul 10, 12:07 pm, ssecorp <circularf...@gmail.comwrote:
pair1 = (student1,student2)
pair2 = (student2,student1)
if (pair1 or pair2) in incompatibles:
Apart from the problems that others have mentioned, the above
statement is NOT doing what you think it is. (pair1 or pair2) will
always produce pair1, because pair1, a tuple of length 2, cannot be
false. So the statement is equivalent to:
if pair1 in incompatibles:
What you want is:
if pair1 in incompatibles or pair2 in incompatibles:

Cheers,
John
Jul 10 '08 #5
I don't fully understand why I have to do this.
On Jul 10, 4:17*am, Robert Kern <robert.k...@gmail.comwrote:
ssecorp wrote:
Im looking into PvsNP:
http://www.claymath.org/millennium/P_vs_NP/
so I thought I'd write the program just to get a feel for it.
But I run into a problem. Why does it all the sudden return None? I
mean I know why the program aborts but I dont understand why the None
is generated all the sudden. Hitting recursion depth isn't reported
with that error.

def validate(placed):
* * *student = round(random.random()*401)
* * *if student in placed:
* * * * *# You need to explicitly return, here:
* * * * *return validate(placed)
* * *else:
* * * * *placed.append(student)
* * * * *return student, placed

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
* that is made terrible by our own mad attempt to interpret it as though it had
* an underlying truth."
* *-- Umberto Eco
Jul 10 '08 #6
On Jul 10, 11:15*pm, ssecorp <circularf...@gmail.comwrote:
I don't fully understand why I have to do this.
Because your function is recursive.

You call your function passing it a list of numbers. It generates a
new number and looks to see if it's in the 'placed' list. If it is, it
calls itself again, but if it isn't, it returns the number & an
updated 'placed'.

Without placing a return before the recursive call to validate, it
calls validate in place, ignores its return result, then drops out of
the conditional to the end of the function, where an implicit 'return
None' occurs.

By returning what validate passes back, you in effect pass it back up
the chain of recursive calls, so the final return will _always_ pass
back the number, list combo you require.

- alex23
Jul 11 '08 #7

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Atul Kshirsagar | last post: by
7 posts views Thread by 5HH575-UAZWKVVP-7H2H48V3 | last post: by
6 posts views Thread by Mike Brown | last post: by
1 post views Thread by Paul Du Bois | last post: by
7 posts views Thread by Girish Sahani | last post: by
10 posts views Thread by est | last post: by
4 posts views Thread by guiromero | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.