Monday, November 23, 2009

Round-Robin Tournament Scheduling

For the last several years, I've held an in-class tournament on the last class day before Thanksgiving. Everybody's mind is elsewhere anyway, so the positive vibes generated by an hour spent hootin' and hollerin' are far more valuable than class content that would be forgotten long before the turkey made it into the oven.

Tomorrow's the big day, so I've spent part of today working out the tournament schedule. As usually seems to be the case, I have a different number of teams this year from past years, so I had to make a new schedule from scratch. I keep forgetting how I did it last time, but I always seem to converge back on the same technique. I finally decided to write down the technique so I can just look it up next year. Also, I'm hoping somebody can tell me what this technique is called, since it can't possibly be original.

Unless I have too many teams, I like to run a round-robin tournament, where everybody plays everybody else. There's a well-known algorithm for scheduling such a tournament by hand. I'll illustrate this algorithm with 6 teams, numbered 0–5. Start by writing the teams down in two rows, as follows:

   0 1 2
   5 4 3
The columns say which teams play each other. In this case, team 0 plays team 5, team 1 plays team 4, and team 2 plays team 3.

Now, leave team 0 in place, but rotate teams 1–5 one position clockwise.

   0 5 1
   4 3 2
In this round, team 0 plays team 4, team 5 plays team 3, and team 1 plays team 2. This process continues for three more rounds:
   0 4 5
   3 2 1

   0 3 4
   2 1 5

   0 2 3
   1 5 4
For an even number of teams, this technique generates a schedule with N−1 rounds, and N/2 games per round. For an odd number of teams, you add an extra dummy team, yielding a schedule with N rounds and (N−1)/2 games per round. In each round, the team scheduled against the dummy gets a bye.

Many games have a slight asymmetry, such as a homefield advantage or a first-move advantage. For my game, the “red” team has a very small advantage over the “blue” team. In tournaments for such games, it is important to balance the number of “home” games and “away” games played by each team. In the above algorithm, this is accomplished by making the top row the home team in odd-numbered rounds and the bottom row the home team in even-numbered rounds. (Note that, when N is even, half the teams will get one extra home game.)

Okay, so the above technique is easy, but it has a major drawback for my purposes, at least when N is odd. Because the tournament must be completed by the end of the class period, I need to be ready to drop games from the schedule if it looks like we're running long. The easiest way to accomplish this is to drop an entire round. But when N is odd, one team has a bye, which means that that team will end up playing a different number of games from everybody else, which in turn can make it difficult to determine the winner of the tournament.

To avoid this problem, I use the following technique. I organize the schedule in N/2 rounds, rounded down if N is odd. In each round (except possibly the last), every team plays twice: one home game and one away game. The rule is that, in round R, team X plays at home against team (X+R) mod N, and away against team (X−R) mod N. (If you don't remember how mod works, it simply means that the team numbers wrap around.) For example, here is a schedule for 7 teams, numbered 0–6.

   Round 1: 0-1 1-2 2-3 3-4 4-5 5-6 6-0

   Round 2: 0-2 1-3 2-4 3-5 4-6 5-0 6-1

   Round 3: 0-3 1-4 2-5 3-6 4-0 5-1 6-2
Each game is listed as HOME TEAM–AWAY TEAM.

If N is even, then the last round is treated specially. As described so far, the last round in an 8-team tournament would look like

   Round 4: 0-4 1-5 2-6 3-7 4-0 5-1 6-2 7-3
This involves repeat games, such as 0-4 and 4-0. To prevent such repeats, we chop off the second half of the last round when N is even.

Again, the advantage of this scheduling algorithm is that I can delete a round on the fly without causing an imbalance in the number of games that each team plays. Deleting a round also maintains the balance between home games and away games for each team, although that's a lesser concern.

Thursday, October 22, 2009

Binomial queues as a nested type

Warning: this is probably only of interest to functional programmers.

Maciej Kotowicz recently asked on the Haskell Cafe mailing list about implementing binomial queues (also known as binomial heaps) using fancy type machinery so that the type-checker can enforce the shape invariants of the data structure. This reminded me of a discussion I had with some colleagues in the summer of 1998 about using nested types to enforce these kinds of invariants. A little digging around in mail archives yielded this email, presented here with some light formatting and a few fixed typos.

I've been playing with binomial queues as a nested type, and I think you'll find the end result interesting.

REVIEW

Let me first quickly review the usual implementation of binomial queues. Recall that a binomial tree has the shape

data Tree a = Node a [Tree a]
A binomial tree of rank k has k children, of ranks k-1 .. 0 (stored in the list in decreasing order of rank). Note that we can combine two heap-ordered binomial trees of rank k to get a heap-ordered binomial tree of rank (k+1) as follows:
combine a@(Node x xs) b@(Node y ys)
   | x <= y    = Node x (b : xs)
   | otherwise = Node y (a : ys)
Now a binomial queue is a list of heap-ordered binomial trees of increasing height (but not necessarily of consecutive ranks). We'll represent the ranks of those trees that are present by their position in the tree. Thus, some ranks will be empty. This could be implemented as
type Binom a = [Maybe (Tree a)]
or somewhat more efficiently as
data Binom a = Nil
             | Zero (Binom a)
             | One (Tree a) (Binom a)
or better still by unboxing the Tree in the One constructor
data Binom a = Nil
             | Zero (Binom a)
             | One a [Tree a] (Binom a)
I won't go over all the operations -- they are amply covered elsewhere. I'll just describe two functions. The first, add, takes a tree and a list (where the tree has the same rank as the first position in the list), and returns a new list. It works basically like the increment function on binary numbers.
add :: Ord a => a -> [Tree a] -> Binom a -> Binom a
add x xs Nil = One x xs Nil
add x xs (Zero h) = One x xs h
add x xs (One y ys h)
  | x <= y    = Zero (add x (Node y ys : xs) h)
  | otherwise = Zero (add y (Node x xs : ys) h)
The merge function is similar and works basically like the addition function on binary numbers.

Finally, the getMin function returns the minimum element of a queue paired with the queue without that element. The helper function getMin_ returns a triple of the minimum element in some suffix of the queue, the list of children associated with that minimum element, and the suffix without that element.

getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)
getMin_ (Zero h) = case getMin_ h of
                     (y,ys,h') -> (y,ys,Zero h')
getMin_ (One x xs Nil) = (x,xs,Nil)
getMin_ (One x xs h) = case getMin_ h of
                         (y,ys,h') | x <= y    -> (x,xs,Zero h)
                                   | otherwise -> (y,ys,One x xs h')

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (list2binom xs Nil) h')

list2binom [] h = h
list2binom (Node x xs : ys) h = list2binom ys (One x xs h)
Note that when getMin receives a list of children, it converts them to a valid binomial queue by reversing the list (and changing each pair of a Node constructor and a (:) constructor to a One constructor).

NESTED REPRESENTATION -- FIRST ATTEMPT

By following the same approach we have been using to design nested datatypes, we get the following representation of binomial queues.

data Binom_ a b = Nil
                | Zero (Binom_ a (Trees a b))
                | One a b (Binom_ a (Trees a b))

type Trees a b = (a, b, b)

type Binom a = Binom_ a ()
Here the list of children
  (Node x3 xs3 : Node x2 xs2 : Node x1 xs1 : Node x0 xs0 : [])
is being represented by the nested triples
  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
(where xsN' is the appropriate conversion of xsN).

All the functions are perfectly straightforward, except for getMin and getMin_ which must incrementally build up the reversing function to convert

  (xs3,xs3', (x2,xs2', (x1,xs1', (x0,xs0', ()))))
to
  One x0 xs0' (One x1 xs1' (One x2 xs2' (One x3 xs3' Nil)))
As a result of building up this reverse function incrementally, this implementation ends up being roughly 10% slower than the original.

INTERLUDE ON REVERSING LISTS

Suppose we want to support the following ADT. We want sequences with three operations:
empty :: ReversableSeq a
cons  :: a -> ReversableSeq a -> ReversableSeq a
rev   :: ReversableSeq a -> [a]
with the obvious semantics. cons must take O(1) time, but rev may take O(n) time. A list is a reasonable implementation with
type ReversableSeq a = [a]
empty = []
cons = (:)
rev = reverse
but, if you think about it, there's a fair amount of interpretive overhead in the pattern matching that reverse performs at every step. Way back in 1985, John Hughes came up with a representation that avoids this overhead:
type ReversableSeq a = [a] -> [a]
empty = id
cons x xs = xs . (x:)
rev xs = xs []
The result of cons 1 (cons 2 (cons 3 empty)) is
id . (3:) . (2:) . (1:)
which, when applied to [] by the rev function, yields [3,2,1]. One way to think of this representation is as lists with "holes" at the ends. The cons operation fills in this hole with an element and another hole, and the rev operation fills in the hole with []. (This is quite similar to difference lists in logic programming...)

Applying this trick to the regular representation of binomial queues yields

data Binom a = Nil
             | Zero (Binom a)
             | One a (Binom a -> Binom a) (Binom a)
which turns out to be about 10% faster than the original representation.

NESTED REPRESENTATION -- SECOND ATTEMPT

Ok, let's try to make a nested datatype out of this. Conceptually, the nesting should keep track of our position in the queue so that we know what rank the current tree has and can't possibly mix up trees of different ranks. We hypothesize some Base type for the beginning of the list, and some type transformer Succ that modifies the type as we move down the queue.

type Base = ???
type Succ b = ???  -- this might need to be Succ a b

type Binom a = Binom_ a Base

data Binom_ a b = Nil
                | Zero (Binom_ a (Succ b))
                | One a (Binom_ a ??? -> Binom_ a ???) (Binom_ a (Succ b))
Now, what should the missing types in the One constructor be? Well, the function (Binom_ a ??? -> Binom_ a ???) represents the children of the current node. If this node is of rank k, then these children are of ranks 0 .. k-1. The function (Binom_ a ??? -> Binom_ a ???) takes a queue starting at rank k and adds the children to the front of it, yielding a queue starting at rank 0. So the ???'s can be filled in as
                | One a (Binom_ a b -> Binom_ a Base) (Binom_ a (Succ b))
or just
                | One a (Binom_ a b -> Binom a) (Binom_ a (Succ b))
Now, what should the types Base and Succ be? It doesn't matter because we never construct data of those types, we simply use the types to discriminate between positions in the queue. So we can define Base and Succ as
type Base = Void
newtype Succ b = S Void
I think this is a very interesting type for several reasons:
  • It includes an arrow type, which we haven't seen much.
  • The RHS of the datatype definition (in fact, just the One constructor) has occurrences of Binom_ at no fewer than three different types
    Binom_ a b
    Binom_ a Base
    Binom_ a (Succ b)
    
    I've seen two before, but not three.
  • It includes types which are never used, but are merely there to capture certain invariants (in this case, that trees of different ranks should never be confused). [2009 Comment: Today, these are called phantom types.] In some ways this might make this type less interesting, but an interesting consequence is that the code satisifes a certain "type erasure" property: if you erase the types from all the functions, you get code for the optimized regular representation.
Because of this "type erasure" property, you might expect it to be just as fast as the optimized regular representation, but in fact it is roughly 10% slower -- or roughly as fast as the original regular representation. This is because the extra types hinder a certain optimization that the programmer might make (and which I did make in the optimized regular representation).

Recall the type of the getMin_ function from the original regular representation, and the way it was used by getMin.

getMin_ :: Ord a => Binom a -> (a, [Tree a], Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (list2binom xs Nil) h')
For the optimized regular representation, this becomes
getMin_ :: Ord a => Binom a -> (a, Binom a -> Binom a, Binom a)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (xs Nil) h')
Now, consider the optimized nested representation. We can't just write
getMin_ :: Ord a => Binom_ a b -> (a, Binom_ a b -> Binom a, Binom_ a b)
because we don't know the rank of the tree that the second component of the triple came from. (Note that if we had existential types, we could write
getMin_ :: Ord a => Binom_ a b -> 
                    (a, exists c. Binom_ a c -> Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge (xs Nil) h')
Some implementations do in fact support existential types, but in limited ways that would carry efficiency costs of their own...)

Instead of returning the children and then applying them to Nil at the end, we apply the children to Nil first, and then return the result, yielding the type

  
getMin_ :: Ord a => Binom_ a b -> (a, Binom a, Binom_ a b)

getMin :: Ord a => Binom a -> (a, Binom a)
getMin h = let (x,xs,h') = getMin_ h
           in (x,merge xs h')
This depends on laziness to evaluate only the children of the final minimum, and not all the children of the temporary minimums along the way. However, this does mean that we build a lot more thunks of the form (xs Nil) along the way. And building these thunks is apparently quite expensive.

2009 Addendum Ralf Hinze considers a similar representation in Section 6 of Numerical Representations as Higher-Order Nested Datatypes. Today, you would probably use fancier type machinery like dependent types or maybe GADTs, but it's still amazing how far you can get with only nested types.