Estoy buscando un algoritmo para generar un cronograma para un conjunto de equipos. Por ejemplo, imagine una temporada deportiva en la que cada equipo juega entre sí, una vez como equipo local y el otro como equipo visitante en el campo de otro equipo.

Generar un conjunto de todos los juegos de la temporada es fácil, si los equipos son una lista de equipos, lo siguiente haría:

set((x, y) for x in teams for y in teams if x != y)

Pero también quiero ORDENAR los juegos en orden cronológico de tal manera que satisfaga la restricción de un horario de juego válido y también se vea "naturalmente aleatorio".

a restricción es que la lista de juegos debe ser agrupable en varias rondas donde cada ronda consta de n / 2 juegos (donde n es el número de equipos) en los que cada equipo está emparejado con otro.

Para que el horario se vea más natural, dos equipos no deben enfrentarse dos veces en rondas consecutivas. Es decir, si (a, b) se juega en una ronda, el juego (b, a) no debe jugarse en la primera.

También, en la medida de lo posible, cada equipo debe jugar en cada ronda como el equipo visitante y las otras rondas como el equipo local. No creo que sea posible cumplir siempre con esta restricción, por lo que es mejor tener algo. Por ejemplo, un equipo no debe jugar 8 juegos en casa y luego 8 partidos fuera de casa.

Abajo es lo que tengo ahora. El principal problema con el algoritmo es que se queda atascado en el ciclo while con bastante frecuencia. Especialmente cuando el número de equipos es 16 o más. También es muy ineficiente porque se basa en el uso de la función de muestra aleatoria y espera hacerlo bien:

from random import sample
def season_schedule_order(teams, pairs):
    n_games_per_round = len(teams) // 2
    last_pairs = set()
    while pairs:
        r_pairs = set(sample(pairs, n_games_per_round))
        # Check that each team is present once in the round.
        r_teams = set(x for (x, y) in r_pairs) | set(y for (x, y) in r_pairs)
        if r_teams != teams:
            continue
        # Check that two teams doesn't face each other again.
        rev_pairs = set((y, x) for (x, y) in r_pairs)
        if rev_pairs & last_pairs:
            continue
        pairs -= r_pairs
        for p in r_pairs:
            yield p
        last_pairs = r_pairs

teams = set(['aik', 'djurgarden', 'elfsborg', 'gais',
             'gefle', 'hacken', 'halmstad', 'helsingborg'])
pairs = set((x, y) for x in teams for y in teams if x != y)
for (ht, at) in season_schedule_order(teams, pairs):
    print '%-20s %-20s' % (ht, at)