Estou procurando um algoritmo para gerar um cronograma para um conjunto de equipes. Por exemplo, imagine uma temporada esportiva em que cada equipe jogue uma com a outra, uma vez como equipe local e a outra como equipe visitante em outro camp

Para gerar um conjunto de todos os jogos da temporada, é fácil, se times for uma lista de times, o seguinte seria:

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

Mas também quero ORDENAR os jogos em ordem cronológica, de forma que satisfaça a restrição de uma programação válida e também pareça "naturalmente aleatório"

A restrição é que a lista de jogos seja agrupável em várias rodadas, onde cada rodada consiste em n / 2 jogos (onde n é o número de equipes) em que cada equipe está emparelhada com outr

Para tornar o cronograma mais natural, duas equipes não devem se enfrentar duas vezes em rodadas consecutivas. Ou seja, se (a, b) for jogado em uma rodada, o jogo (b, a) não deverá ser jogado na ex

Além disso, na medida do possível, todos os times devem jogar todos os outros rounds como o time visitante e os outros rounds como o time da casa. Eu não acho que é possível sempre cumprir essa restrição, por isso é mais bom ter uma coisa. Por exemplo, um time não deve jogar 8 jogos em casa e depois 8 jogos for

Abaixo é o que eu tenho agora. O principal problema com o algoritmo é que ele fica preso no loop while com bastante frequência. Especialmente quando o número de equipes é 16 ou mais. Também é muito ineficiente porque se baseia no uso da função de amostra aleatória e na esperança de acertar:

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)