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\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

 

[Robert Kern]

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

 

[ssecorp]

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]

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

 

[ssecorp]

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

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

 

[alex23]

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