Static-Hashed-Tournament Scheduling Algorithm

Introduction

So the idea here is to come up with a way to id a particular configuration/combination of teams from different sites (and possibly # of courts) and the store several solutions.

Our previous organization has focused on mixing up the teams from the various sites to try to spread them out over a semi-fixed pool layout. If instead we take a more structured approach of ordering the teams by the number of teams from each site, we can come at this more systematically and maybe only solve the problem one time for each case (possibly a couple more to allow tournament repeats where we try to avoid repeating matches held in the previous tournament.

Implementation of this idea is described at Pool_Layout_DB

Team ordering within pool by site association

For this to work, we would need to have a specific way of ordering the teams (by site association) within the pool. The most obvious choice is to take the site with the most kids, drop them in first.

So if we look at the total number of teams we can imagine that we could break that down into ordered sets.

So for a 4 team pool only the following combination of teams/site are available.

4       Only 1 site in this pool (ie: other sites may not have kids in this age division)
31      2 different sites, 3 from one, 1 from the other
22      2 different sites, 2 teams from each
211     3 different sites
1111    4 different sites, 1 team from each sites

So the approach here is to find 1-3 solution sets for each of these possibilities, instead of finding all possible match combos to check against. This approach will not be more efficient for smaller pools, but will yield HUGE efficiencies on the larger pools where the combinatorics of solution sets blows up into crazy large numbers.

Number of courts

The other variable here is the number of courts to use. The default is typically int(floor(#teams/2)), but there are cases where its desirable or necessary to have fewer than that number of courts. One examples would be a celebrity visit, having additional teams with byes would provide more photo ops. Another example would be a field that does not have the capacity for the full number of courts required to minimize byes.

Number of games

The remaining variable is the number of games. This is not quite as important because the really critical component is assigning the matches for each game. When adding games, we want to avoid (or at least minimize) repeated games and collisions. The way to handle this is to maybe just provide a couple additional games slots in the stored template.

Number of Sites

Theoretically, this number of sites involved in a tournament can be large, but it is typically not more than 4. We could easily focus on template building up to that number and provide error messages or prompts if we exceeed that number. Notice that if we can eliminate extra template work even starting in the case of a 5 team pool. This is represented by the number of digits in the combination.

Possible site count breakdowns for larger pools

A couple things here. Have put a * after possibilities that indicate 6 or more teams in a pool. Even 5 is pretty unlikely at this point. Another shortcut I took is that I dont include possibilities where we have more than 10 teams from a single site in the pool. This is primarily because it breaks my simple notation here, but the reality is that its unlikely that those cases will crop up.

5 teams in a pool, site count possibilities, in largest to smallest order

5
41
32
311
221
2111
11111  # 5 sites with one team each in pool, probably dont need to cover...

6 teams in a pool, site count possibilities, in largest to smallest order

6
51
42
411
33
321
3111
222
2211
21111
111111*

7 teams in a pool, site count possibilities, in largest to smallest order

7
61
52
511
43
421
4111
331
322
3211
31111
2221
22111
211111*
1111111*

8 teams in a pool, site count possibilities, in largest to smallest order

8 
71
62
611
53
521
5111
44
431
422
4211
41111
332
3311
3221
32111
311111*
2111111*
1111111*

9 teams in a pool, site count possibilities, in largest to smallest order

9 
81
72,711
63,621,6111
54,531,522,5211,51111
441,432,4311,4221,42111,411111*
333,3321,33111,3222,32211,321111*,3111111*

10 teams in a pool, site count possibilities, in largest to smallest order

10 
91
82,811
73,721,7111
64,631,622,6211,61111
55,541,532,5311,5221,52111,511111*
442,4411,433,4321,43111,4222,42211,421111*,4111111*
3331,3322,33211,331111*,32221,322111*,3211111*,31111111*
22222,222211*,2221111*,22111111*,211111111*

11 teams in a pool, site count possibilities, in largest to smallest order

92,911
83,821,8111
74,731,722,7211,71111
65,641,632,6311,6221,62111,611111*
551,542, 5411,533,5321,53111,5222,52211,521111*,5111111*
443,4421,44111,4331,4322,43211,431111,42221,422111*,4211111*,41111111*
32222,322211*,3221111*,32111111*,311111111*,222221*

12 teams in a pool, site count possibilities, in largest to smallest order

93,921,9111
84,831,822,8211,81111
75,741,732,7311,72111,711111*
66,651,642,6411,633,6321,63111,621111*
552,5511,543,5421,54111,5331,53211,531111*,52221,5221111*
444,4431,4422,44211,441111*,4332,43311,432111*,42222,422211*
3333,33321,333111*,33222,332211*,322221*
222222*

Algorithm

Want to come up with an algorithm to generate the combinations above. Want to highlight combinations that:

• Are unable to have any complete solutions resolved (site with largest number of teams has more teams than all others combined)...
• Combinations that have 5 (or 6) or more separate entities (would represent having more than 5 (or 6) sites at a tournament).

Coded up the basic algorithm in a class recCombSumClass.php and implemented a script to test the thing at recCombSum.php. Should make that a form and then start working on solutions. Using the existing algorithms from the tournament stuff.

Applying the algorithm

So much of the above is just figuring out what solution sets we need. But that doesn't get us a solution set.

Some of the above will be automatically solvable. But others will have to be done manually.

Another problem we have is how to deal with repeated tournaments. We need to have a way to provide multiple solution sets anywhere we think we might have a complete repeat of a tournament.

Have coded up the recursive combinations for the site/team combinations. Will output the above tables in a more useful fashion.

So the general idea is to get solution sets for as many of these as we can. Automatically for the ones we can. Manually solve for others. Maybe just enter the solution sets in a db for later lookups.

When we look at doing large pools, we can see if we have a solution set, if so grab it. If not, skip it and do it the old way.

Pros/Cons

The current algorithm depends on mixing the teams differently for each repeated tournament. This makes the whole tournament placement much more complicated than it needs to be. This method would put teams into pools much more consistently and simply.

The new method would allow us to key one or more solution sets to a pool layout and then apply a fixed solution set.

The team mixing could possibly done just be reordering the teams within each site on repeated tournaments. Possibly just be shifting/rotating the list.

References/Related

• http://www7a.biglobe.ne.jp/~sumnumberplace/31642733/
• http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c15409/Dynamic-Programming-Combination-Sum-Problem.htm
• http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum
• http://blogs.msdn.com/b/hilliao/archive/2010/06/28/count-the-number-of-combinations-that-add-to-a-given-sum-in-an-int-array.aspx