StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Some thoughts, perhaps a solution...</p> <p>Expanding the problem to X players and Y courts, I think we can safely say that when given the choice, we must select the players with the fewest completed matches, otherwise we run the risk of ending up with one player left who can only play every other week and we end up with many empty weeks in between. Picture the case with 20 players and 3 courts. We can see that during round 1 players 1-6 meet, then in round 2 players 7-12 meet, and in round 3 we could re-use players 1-6 leaving players 13-20 until later. Therefor, I think our solution cannot be greedy and must balance the players.</p> <p>With that assumption, here is a first attempt at a solution:</p> <pre><code> 1. Create master-list of all matches ([12][13][14][15][16][23][24]...[45][56].) 2. While (master-list > 0) { 3. Create sub-list containing only eligible players (eliminate all players who played the previous round.) 4. While (available-courts > 0) { 5. Select match from sub-list where player1.games_remaining plus player2.games_remaining is maximized. 6. Place selected match in next available court, and 7. decrement available-courts. 8. Remove selected match from master-list. 9. Remove all matches that contain either player1 or player2 from sub-list. 10. } Next available-court 11. Print schedule for ++Round. 12. } Next master-list </code></pre> <p>I can't prove that this will produce a schedule with the fewest rounds, but it should be close. The step that may cause problems is #5 (select match that maximizes player's games remaining.) I can imagine that there might be a case where it's better to pick a match that <em>almost</em> maximizes 'games_remaining' in order to leave more options in the following round.</p> <p>The output from this algorithm would look something like:</p> <pre><code>Round Court1 Court2 1 [12] [34] 2 [56] -- 3 [13] [24] 4 -- -- 5 [15] [26] 6 -- -- 7 [35] [46] . . . </code></pre> <p>Close inspection will show that in round 5, if the match on Court2 had been [23] then match [46] could have been played during round 6. That, however, doesn't guarantee that there won't be a similar issue in a later round.</p> <p>I'm working on another solution, but that will have to wait for later.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload