Is this a hard problem?

[paulmansour]

In the spirit of the Olympics, consider a set of an even number of teams, say A B C and D.

I want to construct a schedule, a series of rounds, where each team plays in each round, and over all the rounds, each team plays each other team exactly once.

Thus, in the case of four teams A B C and D, I would like something like:

Round Team1 Team2
===== ===== =====
1 A B
1 C D
2 A C
2 B D
3 A D
3 B C

This doesn't seem like it should be especially hard, but I spent more time than I would care to admit trying to solve it for the general case of N teams (where N is even).

I tried generating all combinations using outer product, and then selecting and sorting. I tried repeated reshaping and transposing, all to no avail.

Is this a hard problem or am I missing something?

Any insights or solutions would be appreciated.

Thanks,

Paul

[StephenTaylor]

This is a squib, cos I’m going to bed instead of sitting up coding it. But old-fashioned dances solve similar problems.

I see a recursive solution:

Divide the teams into two columns and pair them. You get n÷2 rounds by rotating one of the columns by 1 position per round. Now each member of the left column has danced with each member of the right column, but with no member of its own column.

Repeat with each column of teams until you reach the end condition, which is a column of 1 team.

SJT

[Roger|Dyalog]

I got lazy and looked it up: http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm. It can be coded in APL as follows.

      ⎕io←0
      rr←{(m,2,⍵÷2)⍴0,(⍳m)⌽(2⍴m)⍴1+⍳m←⍵-1}

      rr 10
0 1 2 3 4
5 6 7 8 9
         
0 2 3 4 5
6 7 8 9 1
         
0 3 4 5 6
7 8 9 1 2
         
0 4 5 6 7
8 9 1 2 3
         
0 5 6 7 8
9 1 2 3 4
         
0 6 7 8 9
1 2 3 4 5
         
0 7 8 9 1
2 3 4 5 6
         
0 8 9 1 2
3 4 5 6 7
         
0 9 1 2 3
4 5 6 7 8

The expression (⍳m)⌽(2⍴m)⍴1+⍳m←⍵-1 can be coded slightly faster as 0 ¯1↓(m,⍵)⍴1+⍳m←⍵-1 with (in my opinion) some lost of clarity.

[StephenTaylor]

Worse than a squib -- simple recursion will work only for lists whose lengths are powers of 2, not for all even numbers.

SJT :-(

[paulmansour]

Roger, thanks.

I should have googled! I'm going to avoid looking at your solution until I've digested the wikipedia article had a go myself and see what I come up with.

Paul

[JohnS|Dyalog]

FYI: There's a slightly amended (by Jay Foad) version of rr in dfns.dws: http://dfns.dyalog.com/n_rr.htm
This animation http://www.devenezia.com/downloads/round-robin/ might also prove helpful.

[Roger|Dyalog]

> FYI: There's a slightly amended (by Jay Foad) version of rr in dfns.dws: http://dfns.dyalog.com/n_rr.htm

I think John meant a corrected version. My version from last night has obvious errors. I should have refrained from posting in the middle of the night just before bed, and I should have QA-ed.

Since I failed to solve it on first try it is a hard problem. ☺

[JohnS|Dyalog]

I wonder how http://dfns.dyalog.com/n_rr.htm might generalise to an ⍺-player game.

[paulmansour]

John and Jay,

Belated thanks for the solution, and adding it dfns. Thanks.

Paul