Calculating golf pairings for a golf weekend

In this previous post, I had given results on how to construct golf foursomes so that 8 people could play 7 rounds in a balanced way (each player played with every other player exactly 3 times). This post is an overview of the method use to produce that result. I used R to product these results.

The main idea is to start with a list of all possible foursomes. For this problem, that’s fairly tangible, as there are only 35 ways of breaking 8 players into 2 foursomes (note that order within the foursome is irrelevant for this). You can see these groupings here

Now the main idea is to repeatedly randomly draw (without replacement) 7 of these foursomes, representing a possible configuration for a weekend. Each time we draw such a grouping of 7 foursomes, we want to calculate some sort of measure to indicate how “good” the random grouping is from the objective of balancing the foursomes as described above. If we run enough of these iterations, we hope to get the “best” pairing.

Basically we are proceeding as

for i in (1:reps){
       Randomly draw 7 foursomes without replacement
       Calculate the measure for this grouping of 7 foursomes
       If the measure is best so far, save
}

 

Defining and calculating the measure for evaluating a foursome

There’s not much theory going on here. But the key observation is that we can represent each grouping of 7 foursomes as a symmetric 8×8 matrix N, where entry n_{ij} represents how many times player i plays player j for the 7 chosen foursomes.
Then, since our objective is to have a balanced grouping, we’d want all non-diagonal entries N to be near the same value. Thus, we just compute the variance of the non-diagonal elements of N, and the matrix with the lowest such variance represents the best grouping of 7 foursomes. Really, for a “perfect” solution, we’d want all non-diagonal entries to be the same number, i.e a variance of 0. This would indicate every player played every other player the same number of times.

Creating the matrix for a grouping

Prior to computing the variance, we , of course, have to build the matrix N. As an example, consider the tenth possible pairing out of the 35 possible foursomes in the input file, i.e. 1,2,5,6,3,4,7,8.

The first four values indicate Players 1,2,5,6 play in Foursome 1 , while Players 3,4,7,8 play in Foursome 2. I wrote a function genivec that would turn this into a 8-tuple p, where p_{i} = 1 if player i is in Foursome 1 and 0 otherwise.

So for our example here, genivec(1,2,5,6,3,4,7,8) -> (1,1,0,0,1,1,0,0)

We can then create another function genmat that will create a sort of 8×8 identity matrix M for this given foursome, where entry m_{ij} = 1 if player i plays with player j in this foursome (and is 0 if they do not play). This is sort of a modified dot product of genivec with itself.
Thus, using the same example foursome as above genmat(genivec(1,2,5,6,3,4,7,8)) =

\left[ \begin{array}{cccccccc} 1&1&0&0&1&1&0&0 \\1&1&0&0&1&1&0&0\\0&0&1&1&0&0&1&1 \\0&0&1&1&0&0&1&1\\1&1&0&0&1&1&0&0 \\1&1&0&0&1&1&0&0\\0&0&1&1&0&0&1&1 \\0&0&1&1&0&0&1&1\end{array} \right]

Now , for any random grouping of 7 matrices selected , we can add the 7 “identity” matrices M_{k} for each of the foursomes, producing an 8×8 matrix N where entry n_{ij} represents the number of times player i plays with player j over the course of the 7 rounds.

It is from this matrix N that we calculate the variance of the non-diagonal elements.

Convergence

I found that comparing would often lead to a “perfect” solution , where each player played every other player exactly 3 times over the 7 rounds. However, it was not always the case. It seems like 70,000 was the minimum number that would guarantee convergence.