[SPOILER] Re: [QUIZ] Perl 'Medium' QOTW - Tournament Schedule

Ian Anderson's Combinatorial Designs and Tournaments (Oxford,
1997) is detailed on the mathematics of tournament schedules.
The classical method is apparently to draw a circle and place one
team in the middle and the other N-1 teams equidistantly around
the circle. (The team in the middle is at the point of infinity).
Then for each round you draw a radian to one of the N-1 teams,
and N/2 - 1 secants perpendicular to the radian joining teams on opposite
sides of the circle. The lines represent the matches.

The solution is another way of generating a round robin design. If we
divide 2n teams into 2 groups of n teams each and arrange them
into 2 concentric circles and for each round rotate the inner
circle around one place, then over n rounds each team in the
inner circle will meet each team in the outer circle, but no team
in the same circle, and vice versa.

If however, one team acts as a shuttle, at each round changing
place with the team in the other circle, bumping teams from the
inner circle into the outer circle and from the outer circle into
the inner circle, sending them back to meet the teams in their
old circle coming up from behind, then all teams appear to meet
every other team in 2n-1 rounds. 

This appears to generate the same rounds that the classical
method mentioned in Anderson's book does in a different
order, though I don't have any proof of the equivalence, or even that
all the teams meet.

Incidentally, although the question said to assume an even number
of teams, if there are an odd number, then we can add a 'bye
team'; not really a team, but what we are matching are not so
much teams as events, ie playing with the 'X' team. The
uniqueness of each meeting and of the bye means that each team
has one and only one bye.

So, here if N is odd, the subroutine adds a bye.
And we represent each round as a hash reference instead of a
array reference.

Here is my solution:

sub allocate_schedule
{
        use integer;
        my $N = shift;
        my $n = ($N+1)/2;
        my @inner = ();
        my @outer = ();
        $outer[$_] = $_ foreach 0 .. $n-1;
        $inner[$_] = $n+$_ foreach 0 .. $n-1;
        $inner[$n-1] = 'bye' if $N % 2;
        my $arrangement;
        for my $twostep ( 0 .. $n )
        {
                my $shufflein;
                for my $position ( 0 .. $n-1 )
                {
                        $$shufflein{$inner[$position]} = $outer[$position];
                        $$shufflein{$outer[$position]} = $inner[$position];
                }
                push @$arrangement, $shufflein;
                my $shuffler = $outer[$n-1];
                $outer[$n-1] = $inner[$n-1];
                $inner[$n-1] = $shuffler;
                unshift @inner, pop @inner;

                my $shuffleout;
                for my $position ( 0 .. $n-1 )
                {
                        $$shuffleout{$inner[$position]} = $outer[$position];
                        $$shuffleout{$outer[$position]} = $inner[$position];
                }
                push @$arrangement, $shuffleout;
                $shuffler = $inner[0];
                $inner[0] = $outer[0];
                $outer[0] = $shuffler;
                push @outer, shift @outer;

        }
        return $arrangement;
}

The shuffler, team n-1, starts on the outer circle at $outer[n-1],
which is rotating anticlockwise. Or the inner circle is rotating
clockwise, same thing.

After the shuffler exchanges places with its counterpart on the
inner list, all teams on the inner circle move one place
clockwise, represented as the shuffler being popped and unshifted
to $inner[0].

Then in the next round, the shuffler moves back to the outer
circle at $outer[0] and as the outer circle moves one place
anticlockwise, the shuffler is shifted and pushed back to the
same relative position in the array it originally had, $outer[n-1]. 


--
Greg Matheson, Taiwan