To solve this problem assign the first seed to play last seeded player in the first round and against a higher seed each subsequent round.

Then simply rely on the round-robin algorithm of rotating an array's values while keeping one static to ensure that everyone plays against each other:

use strict;
use warnings;

my $num_players = 6;

my @players = (1..$num_players);
push @players, 'bye' if @players % 2; # Even number

my $num_rounds = @players - 1;

for my $round (1..$num_rounds) {
    # Fold array to assign matches
    my @matches = map {join('-', sort @players[$_, $#players - $_])} (
+0..@players/2-1);

    # Print Results
    print "$round) " . join(', ', @matches), "\n";
    
    # Rotate last position to second
    splice @players, 1, 0, pop(@players);
}
[download]

Results:

1) 1-6, 2-5, 3-4
2) 1-5, 4-6, 2-3
3) 1-4, 3-5, 2-6
4) 1-3, 2-4, 5-6
5) 1-2, 3-6, 4-5
[download]

Usually I just vote positive. But this time I had to write a little post to say thank you for so many good answers in a very short time.

I'm really impressed. I'm writing a lot of code which is not working for all cases. And you just write some lines of code and it is really working for every case.

One of my first jobs during the dotcom boom was a gaming website that ran tournaments and analyzed statistics. Coming up with algorithms for round robin, single, and double elimination tournaments was one of the first things I did.

A more fun problem is to come up with an algorithm to page a double or single elimination tournament with a large number of seeds. You can of course just do it by hand, but it's more fun if you can configure how many rounds and pairings to show on each page.

Glad we could help.

- Miller

The reason I can think of why you were having specific problems with 6 is because it isn't a power of two. Having set up fencing brackets for tournaments this is definitely true for single elimination, but it might also be true for a round robin if you are essentially running it as a no elimination bracket. I bet you would have problems with 10, 12, 14, evens that aren't a power of two, and all n-1 of those numbers with your code.

Just an idea really, sort of fun to think about, maybe extremely useful for any tournament above 8 or so.

Wow, Dirk80 you just wrote the 800000th post of the monastery!

Hmm I really thought id 100001 was the beginning since id 100000 is (kind of) a user profile.

UPDATE: search form for some really old posts ?node_id=3989;nf=0;Wi;D;M, just hit search button!

Cheers Rolf

This matches pretty well what I would do manually: start with player 1, and assign her to the worst player. Then proceed with the second best, and assign it to the second worst etc.

In the next iteration the best is assigned to the second-worst, thereby decreasing the "distance" by one. At each step I take a look if the "best choice" player is free, and if not, skip to next free player

use strict;
use warnings;
# perl 5.10 only used for say() and infix //
use 5.010;

my $size = shift(@ARGV) // 6;
for my $turn (0.. ($size - 2)) {
    my @players;
    @players[0..($size-1)] = ((1) x $size);
    for (0 .. ($size / 2 - 1)) {
        my $current = $_;
        $current = ($current + 1) % $size until $players[$current];
        $players[$current] = 0;

        my $other = ($size - $turn - $current - 1) % $size;
        $other = ($other - 1) % $size until $players[$other];
        $players[$other] = 0;
        say $current + 1, '-', ($other + 1);
    }
    say '=' x 10;
}
[download]

It seems to work for size 6, haven't tested it for odd sizes.

Update: I've just re-check the output and found that it repeats some pairings. While that might be fixable with a hash of already-seen pairs, I won't bother because there's a more elegant, working solution given in another reply.

On odd sizes, if you allow for the person whose "#", so to speak, has turned up to have a 'bye', then I suspect it works pretty well.

In other words, if player 2 in a 7 player tournament has a bye in round 5, player 3 a bye in round 3 and player 4 a bye in round 1, and writing code to allow byes in odd sized tourneys, the same kind of logic as in the even case should fit.

This chart might explain it better:

1: 7-6-5-4-3-2
2: 6-5-4-3-B-1
3: 5-4-B-2-1-7
4: B-3-2-1-7-6
5: 3-2-1-7-6-B
6: 2-1-7-B-5-4
7: 1-B-6-5-4-3


David.

I think your algorithm is ideal for odd N, but I see an issue for even N. If you look at your 6 contestant matrix, in even numbered rounds, two contestants have byes. To take the 6 nations Rugby Union tournament as an example, it is played over five rounds, not 6, and all teams play on the same week-ends. Every Monday, all teams have played the same number of matches. This isn't to say that your algorithm doesn't work - it does - but this behaviour is an oddity that may not be acceptable.

Regards,

John Davies

It sounds to me as though you are trying to run a Swiss-system tournament. Various methods are described in the wikipedia link. My quick googling didn't find any Perl modules already written, but that doesn't mean they don't exist.

Regards,

John Davies

Oh yes -- Algorithms::Pair::Swiss and Games::Tournament::Swiss are in CPAN. One thing about Swiss system is that it ranks players by their play in the tournament as well as their rating. That 2500 rated IM may end up playing with the experts if he starts losing in a big American Swiss.

Not a Swiss. I thought that too, initially, but Swiss pairs /same scores/ by splitting them in half. It's not a best to worst matching.

David.

Yes, you're right. I didn't read the OP carefully enough. But, if one exists and depending on how it's written, it might still be possible to use a Swiss module to solve this problem. At least some Swiss chess tournaments match scores but then match players by ranking, best v worst. It might be possible to use such an algorithm and insert dummy "scores" and use the ranking to do the rest. But that's putting even more constraints on my originally constrained idea. :-(

Regards,

John Davies

So, what's the preferred sequence of play for player 8? And for player 12?

You are right. The preferred way would be that everyone plays against a player who is furthest away from strength. This was exactly what I tried to do.

My algorithm was first getting all possible matches and also stored the difference between the two players. Then I sorted all matches after this difference and then tried to build the rounds by biggest possible strength difference.

But I had a lot of problems and the algorithm failed for a lot of cases (e.g. 6 players).

I looked at the results of the round robin algorithm and I have to say that the results are really good. Perhaps the sequence for player 8 or 12 is not as perfect as for player 1. But it is good enough for my purposes. And I'm not sure if it is possible to make it better. Because it is important that a player has never to wait (except when he is playing against a bye).

For me it was the most important that the best players play at the end against each other so that it is like a final altough everyone played against everyone.

I even found the round robin algorithm in wikipedia: http://en.wikipedia.org/wiki/Round-robin_tournament. So I think it is a common way to make a tournament according to this algorithm.

You are right. I tried the module Games::Tournament::RoundRobin. It delivers the same result apart from the order of the rounds. The last round is the same as my first round, ...

use strict;
use warnings;

use Data::Dumper;

use Games::Tournament::RoundRobin;

my $schedule = Games::Tournament::RoundRobin->new(v => 6, league => [1
+..6]);

print Dumper($schedule->wholeSchedule());
[download]