StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow do I generate a tournament schedule in Ruby?
text
Body
copied!<p>I have been searching everywhere, including the Stack Overflow archives, for an answer of how to do this, I tried rolling my own, but have come up short, so I decided I would post my request here.</p> <p>I need to take an arbitrary (even) number of items in an array and return with item paired with another item in the array. I need the output of the code to be the same as the output example I have included below.</p> <p>Input:</p> <pre> ('A'..'H').to_a </pre> <p>Output:</p> <pre> [[['A','H'], ['B','G'], ['C','F'], ['D','E']], [['A','G'], ['B','F'], ['C','E'], ['D','H']], [['A','F'], ['B','E'], ['C','D'], ['G','H']], [['A','E'], ['B','D'], ['C','H'], ['F','G']], [['A','D'], ['B','C'], ['E','G'], ['F','H']], [['A','C'], ['B','H'], ['D','G'], ['E','F']], [['A','B'], ['C','G'], ['D','F'], ['E','H']]] </pre> <p>Any ideas?</p> <p>Here's what I have done so far. It's a bit dirty, and it's not returning in the order I need.</p> <pre> items = ('A'..'H').to_a combinations = [] 1.upto(7) do |index| curitems = items.dup combination = [] 1.upto(items.size / 2) do |i| team1 = curitems.delete_at(0) team2 = curitems.delete_at(curitems.size - index) || curitems.delete_at(curitems.size - 1) combination << [team1, team2] end combinations << combination end pp combinations </pre> <p>The output is close, but not in the right order:</p> <pre> [[["A", "H"], ["B", "G"], ["C", "F"], ["D", "E"]], [["A", "G"], ["B", "F"], ["C", "E"], ["D", "H"]], [["A", "F"], ["B", "E"], ["C", "D"], ["G", "H"]], [["A", "E"], ["B", "D"], ["C", "H"], ["F", "G"]], [["A", "D"], ["B", "C"], ["E", "G"], ["F", "H"]], [["A", "C"], ["B", "H"], ["D", "E"], ["F", "G"]], [["A", "B"], ["C", "G"], ["D", "H"], ["E", "F"]]] </pre> <p>You'll notice that my code gets me two D<->H combinations (last line and second line) and that won't work.</p> <p><strong>My understanding of the OP's requirements [FM]:</strong></p> <ul> <li>Given <code>N</code> teams (for example, 8 teams: <code>A..H</code>).</li> <li>Create a tournament schedule, consisting of <code>R</code> rounds of play (7 in our example) and <code>G</code> games (28 in our example).</li> <li>Where every team plays every other team exactly once.</li> <li>Where every team plays once in each round.</li> <li>And (the hard part) where the ordering of games within a round works like this:</li> <li>The top-ranked team (A) plays the low-ranked team (H) first.</li> <li>If a candidate matchup is rejected for violating the no-repeat rule, put the low-ranked team on the "back-burner" and form the other matchups first. Then matchup the back-burner teams using the same rules. (For example: in Round 2, the first candidate matchup, <code>A-H</code>, is rejected as a repeat, so Game 1 will be <code>A-G</code>, and <code>H</code> will sit on the back burner, to be paired with <code>D</code> as the last game in the round).</li> <li>When adding teams to the back-burner, add them to the front of that list (i.e., preserve rank ordering on the back-burner as well).</li> <li><strong>Note</strong>: Round 5 is the tricky one. The first 2 games are straightforward. The 3rd game would then be <code>E-H</code>; however, that creates a scenario where the 4th game would be a repeat (<code>F-G</code>). So the algorithm needs to backtrack, reject the <code>E-H</code> pairing and instead go for <code>E-G</code> in the 3rd game.</li> </ul>

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