man@bocar.UUCP (M Nevar) (11/14/85)
I am in need of an algorithm to devise a basketball schedule. For example, we have 12 teams in our league (but it could go up or down at any point). I need an algorithm to have each team play every other team one time. All games are played on Sunday, so there are six games going on at one time, one each on courts 1 thru 6. Then, the next week, we have six more games, and so on until 11 weeks have passed. I know Knuth must have written an algorithm for this, but I can't find it. If you have any help at all, please send mail to me, as I don't read this newsgroup too often. Thanks, Mark Nevar
stevev@tekchips.UUCP (Steve Vegdahl) (11/15/85)
> I am in need of an algorithm to devise a basketball schedule. For example, > we have 12 teams in our league (but it could go up or down at any point). > I need an algorithm to have each team play every other team one time. > All games are played on Sunday, so there are six games going on at one time, > one each on courts 1 thru 6. Then, the next week, we have six more games, and > so on until 11 weeks have passed. I know Knuth must have written an algorithm > for this, but I can't find it. If you have any help at all, please send mail > to me, as I don't read this newsgroup too often. Algorithms and Knuth notwithstanding, I learned this from my 7th grade P.E. teacher: Assume you have an odd number of teams, 2N+1. Write the names of the first N teams horizontally across the page. Write the names teams N+1 through 2N below those of 1 through N respectively. Write the names of team 2N+1 in a box marked "BYE". The pairings of the teams for the first round are the vertical pairs. For the second round: 1. shift the top row right one 2. shift the bottom row left one 3. the last team in the top row goes to BYE 4. the first team in the bottom row goes to the first position in the top row 5. the BYE team goes to the last position in the bottom row For the third round, apply steps 1-5 to the results of the second round. For the Kth round, apply steps 1-5 to the results of the (K-1)th round. In other words, you rotate the teams as if they were a volleyball team with N players in the first row and N+1 players in the second row: X --> X --> X --> ... --> X --\ BYE ^ \ | ! X <-- X <-- X <-- ... <-- X <-- X Example 1: For seven teams Round 1: 1 2 3 BYE | | | 4 5 6 7 Round 2: 4 1 2 BYE | | | 5 6 7 3 Round 3: 5 4 1 BYE | | | 6 7 3 2 Round 4: 6 5 4 BYE | | | 7 3 2 1 Round 5: 7 6 5 BYE | | | 3 2 1 4 Round 6: 3 7 6 BYE | | | 2 1 4 5 Round 7: 2 3 7 BYE | | | 1 4 5 6 If you have an even number of teams, 2N, figure a schedule for 2N-1 teams, and let the (2N)th team play the team in the BYE position during each round. Example 2: For six teams Round 1: 1 2 6 <<-- note that the position of team 6 (the | | | "BYE" team) remains the same while the 3 4 5 other teams rotate Round 2: 3 1 6 | | | 4 5 2 Round 3: 4 3 6 | | | 5 2 1 Round 4: 5 4 6 | | | 2 1 3 Round 5: 2 5 6 | | | 1 3 4 Happy Scheduling!! Steve Vegdahl Computer Research Lab. Tektronix, Inc. Beaverton, Oregon