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