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
--
http://mail.python.org/mailman/listinfo/python-list
