Is this a hard problem?
9 posts
• Page 1 of 1
Is this a hard problem?
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
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
- paulmansour
- Posts: 420
- Joined: Fri Oct 03, 2008 4:14 pm
Re: Is this a hard problem?
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
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
-
StephenTaylor - Posts: 31
- Joined: Thu May 28, 2009 8:20 am
Re: Is this a hard problem?
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.
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.
⎕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.
- Roger|Dyalog
- Posts: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Is this a hard problem?
Worse than a squib -- simple recursion will work only for lists whose lengths are powers of 2, not for all even numbers.
SJT :-(
SJT :-(
-
StephenTaylor - Posts: 31
- Joined: Thu May 28, 2009 8:20 am
Re: Is this a hard problem?
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
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
- paulmansour
- Posts: 420
- Joined: Fri Oct 03, 2008 4:14 pm
Re: Is this a hard problem?
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.
This animation http://www.devenezia.com/downloads/round-robin/ might also prove helpful.
- JohnS|Dyalog
Re: Is this a hard problem?
> 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. ☺
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. ☺
- Roger|Dyalog
- Posts: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Is this a hard problem?
I wonder how http://dfns.dyalog.com/n_rr.htm might generalise to an ⍺-player game.
- JohnS|Dyalog
Re: Is this a hard problem?
John and Jay,
Belated thanks for the solution, and adding it dfns. Thanks.
Paul
Belated thanks for the solution, and adding it dfns. Thanks.
Paul
- paulmansour
- Posts: 420
- Joined: Fri Oct 03, 2008 4:14 pm
9 posts
• Page 1 of 1
Return to Functional Programming
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group