[Tutor] A (not so) simple question? Round Robin

[Gregor Lingl]

Yesterday I posted a solution to the 'round-robin'-problem asked for
by Adam Gordon.

This solution (shown below) delivers solutions to the "test-data" of the

problem-setting (i. e. for up to 10 teams) immediately.

However, for a solution for 12 teams it needs 4 secs (on my machine),
and for 14 teams 2400 secs. Sort of exponential runtime-behaviour.

Consequently arises the question not only for a more beautiful program,
but also for a more efficient algorithm (for there are certainly
competitions with more than 14 teams).

Seems interesting to me (although it probably is a so called 'well
known'
problem.)

Well known to somebody of you?

With curiosity
Gregor Lingl



> Here is a quick and dirty solution. Not very Pythonesque, more a
> classical approach.
> Take it as a challenge for Pythonistas to find a more *beautiful* one.
>
> ( http://www.lowerstandard.com/python/beautycontest.txt )
>
> def roundrobin(n):
>     # setup table
>     global table
>     table = [range(n)]
>     for i in range(1,n):
>         row = [i]
>         while len(row)<n: row.append(0)
>         table.append(row)
>     # perform recursive brute search
>     findround(1,2,n)
>     # output in a dirty manner:
>     for row in table: print row
>
> def findround(row,col,dim):
>     global table
>     candidates = range(dim) # candidates for round to play the game
>     # remove candidates already in the same row
>     for i in range(col): candidates.remove(table[row][i])
>     # remove candidates in rows already constructed
>     for i in range(row):
>         if table[i][col] in candidates:
> candidates.remove(table[i][col])
>     for i in candidates:
>         # try round nr. i
>         table[row][col]=i
>         table[col][row]=i
>         if (row == dim-2) and (col == dim-1):
>             # everything found
>             return 1
>         if col < dim - 1:
>             if findround(row,col+1,dim):
>                 return 1
>         elif row < dim - 2:
>             if findround(row+1,row+2,dim):
>                 return 1
>         # undo the try
>         table[row][col]=0
>         table[col][row]=0
>     # no success
>     return 0
>
> # an now call for instance:
>
> roundrobin(10)