Necesito generar todos los emparejamientos posibles, pero con la restricción de que un emparejamiento en particular solo ocurre una vez en los resultados. Así por ejemplo:

import itertools

for perm in itertools.permutations(range(9)):
    print zip(perm[::2], perm[1::2])

genera todas las permutaciones posibles de dos pares; Aquí hay un pequeño subconjunto de la salida:

...
[(8, 4), (7, 6), (5, 3), (0, 2)]
[(8, 4), (7, 6), (5, 3), (1, 0)]
[(8, 4), (7, 6), (5, 3), (1, 2)]
[(8, 4), (7, 6), (5, 3), (2, 0)]
[(8, 4), (7, 6), (5, 3), (2, 1)]
[(8, 5), (0, 1), (2, 3), (4, 6)]
[(8, 5), (0, 1), (2, 3), (4, 7)]
[(8, 5), (0, 1), (2, 3), (6, 4)]
[(8, 5), (0, 1), (2, 3), (6, 7)]
[(8, 5), (0, 1), (2, 3), (7, 4)]
[(8, 5), (0, 1), (2, 3), (7, 6)]
[(8, 5), (0, 1), (2, 4), (3, 6)]
[(8, 5), (0, 1), (2, 4), (3, 7)]
[(8, 5), (0, 1), (2, 4), (6, 3)]
...

¿Cómo puedo filtrarlo más para que solo vea (8,4) una vez (en todas las permutaciones filtradas), y (8,5) solo una vez, y (0,1) solo una vez, y (4,7) ) solo una vez, etc.?

Básicamente quiero las permutaciones de modo que cada emparejamiento de dos elementos ocurra solo una vez.

Apuesto a que hay un itertool adicional que resolvería esto, pero no soy lo suficientemente experto como para saber qué es.

Actualizar: Gareth Rees está en lo cierto, era completamente inconsciente de que estaba tratando de resolver el problema del round-robin. Tengo una restricción adicional que es que lo que estoy haciendo es agrupar personas para ejercicios de programación en parejas. Por lo tanto, si tengo un número impar de personas, debo crear un grupo de tres para incluir a una persona impar en cada ejercicio. Mi pensamiento actual es (1) hacer un número par de personas agregando una persona invisible. Luego, después del emparejamiento, encuentre a la persona emparejada con la persona invisible y colóquela al azar en un grupo existente para formar un equipo de tres. Sin embargo, me pregunto si todavía no hay un algoritmo o ajuste para el round-robin que haga esto de una mejor manera.

Actualización 2: La solución de Theodros produce exactamente el resultado correcto sin la falta de elegancia poco detallada que describo anteriormente. Todos han sido increíblemente útiles.