TypeError, I know why but not how!?

[ssecorp]

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\Pr ogs\PNP\pnp.py" , line 34, in <module>
gen(50)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 32, in gen
return generateList([], [(1,10),(4,272), (34,442),(112,4 2)], [],
rooms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 27, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 27, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 27, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 27, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 27, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 25, in generateList
room, placed = pair(incompatib les, placed)
File "C:\Python25\Pr ogs\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.ra ndom()*401)
if student in placed:
validate(placed )
else:
placed.append(s tudent)
return student, placed

def pair(incompatib les, placed):
student1, placed = validate(placed )
student2, placed = validate(placed )
pair1 = (student1,stude nt2)
pair2 = (student2,stude nt1)
if (pair1 or pair2) in incompatibles:
placed.remove(s tudent1)
placed.remove(s tudent2)
pair(incompatib les, placed)
else:
return pair1, placed

def generateList(do rmlist,incompat ibles, placed, rooms):
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatib les, placed)
dormlist.append (room)
generateList(do rmlist,incompat ibles,placed,ro oms)
else:
return dormlist

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

gen(50)


-------------------------------------------------------------------------------------------------------------------
some tests inserted:


import random

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

def pair(incompatib les, 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,stude nt2)
pair2 = (student2,stude nt1)
if (pair1 or pair2) in incompatibles:
placed.remove(s tudent1)
placed.remove(s tudent2)
pair(incompatib les, placed)
else:
return pair1, placed

def generateList(do rmlist,incompat ibles, placed, rooms):
## print dormlist
## print placed
## print "---------------------------------------------------"
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatib les, placed)
dormlist.append (room)
generateList(do rmlist,incompat ibles,placed,ro oms)
else:
return dormlist

def gen(rooms):
return generateList([], [(1,10),(4,272), (34,442),(112,4 2)], [],
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\Pr ogs\PNP\pnp.py" , line 44, in <module>
gen(50)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 42, in gen
return generateList([], [(1,10),(4,272), (34,442),(112,4 2)], [],
rooms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 37, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 37, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 37, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 37, in generateList
generateList(do rmlist,incompat ibles,placed,ro oms)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 35, in generateList
room, placed = pair(incompatib les, placed)
File "C:\Python25\Pr ogs\PNP\pnp.py" , line 17, in pair
student1, placed = x
TypeError: 'NoneType' object is not iterable

[Robert Kern]

Re: TypeError, I know why but not how!?

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.ra ndom()*401)
if student in placed:
# You need to explicitly return, here:
return validate(placed )
else:
placed.append(s tudent)
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

[A.T.Hofkamp]

Re: TypeError, I know why but not how!?

On 2008-07-10, ssecorp <circularfunc@g mail.comwrote:

>
def validate(placed ):
student = round(random.ra ndom()*401)
if student in placed:
validate(placed )
else:
placed.append(s tudent)
return student, placed
>
def pair(incompatib les, placed):
student1, placed = validate(placed )
student2, placed = validate(placed )
pair1 = (student1,stude nt2)
pair2 = (student2,stude nt1)
if (pair1 or pair2) in incompatibles:
placed.remove(s tudent1)
placed.remove(s tudent2)
pair(incompatib les, placed)
else:
return pair1, placed
>
def generateList(do rmlist,incompat ibles, placed, rooms):
if len(dormlist) < (rooms + 1):
room, placed = pair(incompatib les, placed)
dormlist.append (room)
generateList(do rmlist,incompat ibles,placed,ro oms)
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("Thi s 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

[ssecorp]

Re: TypeError, I know why but not how!?

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?

[John Machin]

Re: TypeError, I know why but not how!?

On Jul 10, 12:07 pm, ssecorp <circularf...@g mail.comwrote:

pair1 = (student1,stude nt2)
pair2 = (student2,stude nt1)
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

[ssecorp]

Re: TypeError, I know why but not how!?

I don't fully understand why I have to do this.


On Jul 10, 4:17 am, Robert Kern <robert.k...@gm ail.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.ra ndom()*401)
     if student in placed:
         # You need to explicitly return, here:
         return validate(placed )
     else:
         placed.append(s tudent)
         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

[alex23]

Re: TypeError, I know why but not how!?

On Jul 10, 11:15 pm, ssecorp <circularf...@g mail.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