алгоритм для генерации расписания для набора команд. Например, представьте себе спортивный сезон, в котором каждая команда играет друг с другом, однажды как домашняя команда, а другая - как команда посетителя на поле другой команды.

Создать набор всех игр в сезоне легко, если бы команды представляли собой список команд, то можно было бы сделать следующее:

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

Но я также хочу ЗАКАЗАТЬ игры в хронологическом порядке таким образом, чтобы они удовлетворяли ограничениям действующего расписания игр и выглядели «естественно случайными».

Ограничение состоит в том, что список игр должен быть сгруппирован по числу раундов, где каждый раунд состоит из n / 2 игр (где n - количество команд), в которых каждая команда соединяется с другой.

Чтобы расписание выглядело более естественным, две команды не должны встречаться друг с другом дважды подряд. То есть, если (a, b) играется в одном раунде, игра (b, a) не должна вестись во внешнем.

Также, насколько это возможно, каждая команда должна играть в каждом последующем раунде, как в гостевой команде, так и в других. Я не думаю, что всегда можно выполнить это ограничение, поэтому лучше иметь такую ​​вещь. Например, одна команда не должна играть 8 домашних игр, а затем 8 выездных.

Ниже то, что я получил сейчас. Основная проблема с алгоритмом заключается в том, что он часто застревает в цикле while. Особенно, когда количество команд составляет 16 и более. Это также очень неэффективно, потому что основывается на использовании функции случайной выборки и в надежде сделать это правильно:

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)