[Layton is my Homeboy]

Now that we have a general approach, we can start to get a bit more technical.

For this discussion, I am going to start at Step 2 (creating a menu of blocks). I will come back to step 1 later on in the thread (as I will discuss, I actually think that step 1 is the most difficult step of this solution).

Assumptions

Since we are skipping step 1, we will make a few assumptions about the data that we theoretically generated in that step.

We will assume that step 1 generated a full pairings/series matrix that tells us which opponents each team is supposed to play throughout the year. It may or may not be the case all teams play each other during the season. For example, if we have just one division in one subleague, then all teams in that division will play each other. By contrast, if we have an MLB-type of setup, then not every team will play each other due to the way that interleague play works.

We will also assume, based on the schedule parameters, that we know which division and subleague each team is in. As a result, whenever we put two teams together into a pairing, we will be able to determine whether that pairing represents a divisional series, a league series, or an interleague series.

Creating a Menu of Blocks

At this stage of the solution, we are trying to create a complete menu of feasible blocks that we can later use to construct the schedule. As a refresher, a block is defined as follows:

Originally Posted by Layton is my Homeboy

A block is a set of pairings, such that every team in the league appears exactly once in one of the pairings in the block. For example, if there are four teams in the league, then one possible block would be {{1,2},{3,4}}. A block is unfinished if it consists of pairings. A block is finished if it consists of series (that is, pairings where the home and away values and a series length has been assigned). A feasible block is one in which all of the pairings are feasible.

So, our goal is to create a menu of every feasible block, based on the schedule parameters. Later on, we will select blocks from this menu to construct a feasible stack. The blocks that we will create at this stage may be used more than once in the stack.

At this stage, we are only dealing with unordered pairings. In other words, we don't care at this stage which teams are the "home" teams and which are the "away" teams. We just care about creating blocks satisfy two conditions: (1) every team in the league appears once and only once within the block; and (2) each pairing consists of two teams that are supposed to play each other (according to the schedule parameters).

In addition to creating a comprehensive menu of blocks, we are going to assign a desirability score to each block. Later, when we are selecting blocks to put together in a stack, we will try to select the most desirable blocks whenever possible.

So, what is a "desirable" block? A block consists of pairings, some of which might be divisional pairings, some of which might be league pairings, and some of which might be interleague pairings. In my view, a desirable block is one that is as homogeneous as possible. In other words, we want all of the pairings in the block (or as many of them as possible) to share the same type.

The reason that this is desirable is that we want to simplify the schedule-making process as much as possible. Having mixed game types in every block makes scheduling harder, because it is more difficult to select a bunch of mixed type blocks that add up to every team playing the correct number of games.

Homogeneous blocks will also help us with optimization later on in the solution. For example, we want to have mostly divisional games late in the season. Having a block that consists of mostly divisional games will help us accomplish this. Similarly, we don't want too many interleague games in the late season. Having an all-interleague block somewhere in the early season will help us with that.

Of course, it won't always be possible for every block to have only a single type of game. In fact, with Houston moving to the AL West next season, the real MLB schedule will be moving to a format in which there will always be at least one interleague game throughout every block in the schedule. So, instead of limiting ourselves just to single-game-type blocks, we will simply prefer blocks that are mainly a single type.

Desirability is based on homogeneity. So, to calculate the desirability score, we are going to add up the total number of divisional, league and interleague games in each block. Desirability is equal to the maximum value out of those three totals.

If there are 10 pairings in a block, then an optimally desirable block is one that consists of 10 divisional pairings or 10 league pairings or 10 interleague pairings. Any of those blocks will have a desirability score of 10. A block that has 7 divisional pairings, 2 league pairings, and 1 interleague pairing has a desirability score of 7. Given a choice between the '10' block and the '7' block, we will add the 10 block to the stack.

We can create the menu of blocks by looping through all of the available pairings for each 'slot' in the block. Because the order of the pairings within the block does not matter, we will filter out equivalent permutations (for example {{1,2},{3,4}} is equivalent to {{3,4},{1,2}}. This will limit our search space and save on processing. We will also filter out blocks that are not feasible (for example, blocks where team 1 appears in two different pairings).

Whenever we identify a feasible block, we will apply a desirability function and store the result in the block's data structure so that we can use it later.