title: Generating natural schedule for a sports league
body: <p>I'm looking for an algorithm to generate a schedule for a set of
  teams. For example, imagine a sports season in which each team plays
  each other, one time as home team and the other as a visitor team on
  another teams field.</p>
  
  <p>To generate a set of all games in the season is easy, if teams is a
  list of teams the following would do:</p>
  
  <pre><code>set((x, y) for x in teams for y in teams if x != y)
  </code></pre>
  
  <p>But I also want to ORDER the games in chronological order in such a
  way that it satisfies the constraint of a valid game schedule and also
  looks "naturally random".</p>
  
  <p>The constraint is that the game list should be groupable into a number
  of rounds where each round consists of n / 2 games (where n is the
  number of teams) in which each team is paired with another one. </p>
  
  <p>To make the schedule look more natural, two teams should not face each
  other twice in consecutive rounds. That is, if (a, b) is played in one
  round, the game (b, a) should not be played in the ext one.</p>
  
  <p>Also, as much as possible every team should play every other round as
  the away team and the other rounds as the home team. I don't think it
  is possible to always fulfill this constraint, so it is more a nice to
  have thing. For instance, one team shouldn't play 8 home games and
  then 8 away games.</p>
  
  <p>Below is what I got now. The main problem with the algorithm is that
  it gets stuck in the while-loop quite often. Especially when the
  number of teams is 16 or more. It also is very inefficient because it
  builds on using the random sample function and hoping to get it right:</p>
  
  <pre><code>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 &amp; 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)
  </code></pre>