In sports tournaments, several teams compete with each other, and in the end, it will rank according to the final table of competitions. The results from the tournament will form the final tables. Because each match can obtain different results, a tournament can achieve different final tables. This article presents a systematic method for generating all possible scenarios for the final tables that a football tournament can achieve. In this research, we have only used the teams' results to produce the final tables, and other issues such as the number of goals scored or the goal difference have not been addressed. The proposed recursive method is suitable for functional programming and implemented using Haskell programming Language.
Article
Production of the Final Score Tables of the Soccer Tournaments using Functional Programming
https://doi.org/10.21203/rs.3.rs-1495052/v2
This work is licensed under a CC BY 4.0 License
Version 2
posted
You are reading this latest preprint version
Tournament
Final Table
Functional Programming
Combinatory
Sports competitions are topics that researchers have been addressing for the past fifty years [1–4]. These investigations have been studied from various perspectives. Tournaments at the beginning were interesting from the perspective of the distance between the teams. Most of these studies focused on leagues [5] on the Round-Robin tournaments [6–8]. Most research has been conducted on the concept of the graph and adjacent matrices. Moon [9] and Donoghue [10] dials about the basic concepts of tournaments. Reid and Beineke [11] have researched tournaments and graph theory. Anderson [12] was worked in combinatorial design and tournaments.
Also, the tournaments have been considered from the perspective of the results. Hemasinha [13] provided an algorithm for sequencing the scores of each match according to the number of teams. Furthermore, in Gervacio [14], Mathsen and Sarangi [15] researched and designed different algorithms for generating score sequences. Hudry and Charon [16] offered the exact method for solving the problems of the linear weighted tournament. Various methods have been developed for various sports disciplines, including soccer [17–19], Baseball [20], and chess [21].
In the football tournament, each team plays only once with all the other teams at the tournament, and can be obtained one of the Win (W), Draws (D), and Losses (L) results. Moreover, in the end, the final table is created based on the results of all games. Three points draw 1 point for every win, and each loss is not entitled to any point.
This paper aims to design all the possible states of final tables in a football tournament by n teams. Here we will assume that each team plays once with other teams in a Round-Robin tournament, and we will get all the possible final tables at the end of the tournament. This table should calculate points based on the team's game results and then sort them according to the points. In producing these tables, no attention is paid to the team's position. The only goal is to get all the cases of the final tables, regardless of the team's ranking in the table. Also, in the production of tables, parameters such as the number of Goals or Goals Difference are not considered. In special cases of a table, points of some rows in the table can be equal. It may even, equality of points is also obtained from gaining different results, like earned points from two wins, zero draws and two losses with earned points from one win, three draws and zero lost (Three points for wins and one point for a draw and zero points for losing and nine points for each sample states). In this case, various permutations of related rows to these cases, Leads to the generation (creation) of new tables.
Football tournaments are round-robin competitions between at least three teams. Since each team competes with all the teams in a tournament, the total number of tournament games is directly related to the number of teams participating. In some competitions, such as the World Cup, the number of teams in each group is usually four, and in some tournaments, such as national league competitions, this number can reach 16 or even 20 teams. Table 1 shows the final standing of group B in FIFA World Cup 2018.
| Group B | P | W | D | L | F | A | Pts |
|---|---|---|---|---|---|---|---|
| Spain | 3 | 1 | 2 | 0 | 6 | 5 | 5 |
| Portugal | 3 | 1 | 2 | 0 | 5 | 4 | 5 |
| Iran | 3 | 1 | 1 | 1 | 2 | 2 | 4 |
| Morocco | 3 | 0 | 1 | 2 | 2 | 4 | 1 |
The related game results of Table 1 are shown in Table 2.
| Team | Spain | Portugal | Iran | Morocco |
|---|---|---|---|---|
| Spain | - | D | W | D |
| Portugal | D | - | D | W |
| Iran | L | D | - | W |
| Morocco | D | L | L | - |
In a tournament with four teams, six games are played, and each game can have one of three results (W, D, L). Depending on the results obtained and considering 3 points for W, 1 point for D, and 0 points for L, the final table for that tournament can be calculated so that the teams are ranked in descending order based on the points earned. Therefore, in a four-team tournament, the total number of possible causes for the results is 36 =729, and each of these cases can produce a final table. Given that the number of matches increases sharply as the number of teams increases, the total possible causes for the final tables will be very high. For example, by increasing only two teams in a six-team tournament, the number of games will be 15, and the total number of possible situations for the results will be 315 = 14,348,907.
If the final tables are created only according to the results of the games and the names of the teams are not considered, many tables may be duplicated so that the production of all final (non-duplicate) table scenarios becomes an NP problem. Table 3 shows a rapid increase in possible situations for calculating the final tables in tournaments.
This article presents a systematic method for generating final tables and implementing them using Haskell's functional programming language.
| Number of teams | Number of games | Possible scenarios Results | Number of final tables | Valid states (%) | Invalid states (%) |
|---|---|---|---|---|---|
| 3 | 3 | 27 | 7 | ||
| 4 | 6 | 729 | 40 | ||
| 5 | 10 | 59,049 | 404 | ||
| 6 | 15 | 14,348,907 | 6317 | ||
| 7 | 21 | 10,460,353,203 | 131288 | ||
| 8 | 28 | 22,876,792,454,961 | 3366444 |
Tournament tables hold some standing values based on the results and games' scores. The results of the games can be a win (W), a draw (D), or a loss (L) which is called WDL. The results and the number of goals scored also used to calculate points. From the home team's perspective, the result of a game is represented by a unique value of 0, 1, or 2, which corresponds to a draw, win, or loss, respectively.
There can always be a certain number of teams in a tournament with a certain number of WDL values for each team. However, the same is not true for the number of FA values, although we may practically restrict it to moderate values. We denote a state to consist only of the WDL values of all participating teams, excluding their FA values.
In the results tables of every tournament, there are cases in which each team has the same WDL. We can generate all of these states by taking the number of teams in the tournament.
Definition 1
For a tournament with n teams, situations can be considered in which all teams have the same (equal) score. A set containing similar values to rows can be created for these cases. This set can be defined as follows.
$$S=\left\{\right(i,n-i*2-1,i\left)\right|i\in \{0..\left(n-1\right)div2\}\}$$
.
It is known that this set has (n-1) div 2 members.
Consider a tournament in which all teams have not any win. Therefore, they have not lost. Hence there are W = 0 and L = 0 for each team. In this case, each team has (n-1) Draw, and thus we have (0, n-1,0) for all rows in the result table. Obviously, for all tournaments with team n, there is at least one result table with the same WDL in each row as follows.
$$\left(\begin{array}{ccc}0& n-1& 0\\ 0& n-1& 0\\ \begin{array}{c}0\\ ..\\ 0\end{array}& \begin{array}{c}n-1\\ ..\\ n-1\end{array}& \begin{array}{c}0\\ ..\\ 0\end{array}\end{array}\right)$$
Another case is that each team has only one win. All teams must have one loss in such a situation and draw the rest of their games for all rows to be the same. Similarly, if we assume k wins for each team, the number of losses and the number of draws will equal k and n-k*2 − 1, respectively. This situation is shown below.
$$\left(\begin{array}{ccc}k& n-k*2-1& k\\ k& n-k*2-1& k\\ \begin{array}{c}k\\ ..\\ k\end{array}& \begin{array}{c}n-k*2-1\\ ..\\ n-k*2-1\end{array}& \begin{array}{c}k\\ ..\\ k\end{array}\end{array}\right)$$
According to this definition, we can easily develop a function called sameWDL in Haskell according to list 1.
|
\(sameWDL :: Int \to \left[\left(Int, Int, Int\right)\right]\) \(sameWDL n =\left[k,n-k*2-a,k\right)|k\leftarrow \left[0\cdots div \left(n=1\right) 2\right]]\) List 1. sameWDL function for generating final tables with the same rows. |
But final tables are not limited to tables with the same rows. In a tournament, one of the W, D, or L results is obtained in each match, effective in the rows related to both teams. By applying all the results obtained in the competitions, a set of all the final tables are created. The issue is addressed from Result-based, Score-based, and WDL-based perspectives to obtain all the results of the competitions. Considering the results of all games from a Result-based perspective is a simple method for organizing final tables. Since the state of a tournament table is derived from the results of the games, it can evaluate possible results of all the games played in a tournament and determine all different states of the tournament table. For n teams, a tournament includes \(\frac{n\left(n-1\right)}{2}\) games, and a game can have three different results. Therefore, this approach needs to evaluate \({3}^{\frac{n(n-1)}{2}}\) sets of game results. Definition 2: A tournament with n team must have the following set of games: \(P=\left\{{T}_{i,j}\right|i,j\in \{\text{1,2},..N\},and,i<j\}\), as i, j denotes the team numbers that play together.
The result of a game between two teams is differently determined for home and away teams. In general, if the game Gab between Ta and Tb results in a win, draw or loss, Rab will be 1, 0, or 2, and Rba will be 2, 0, or 1, respectively. For the conversion of Rab into Rba, we can use the relation 1.
Rba = (Rab+1)/2 + (Rab mod 2) (1)
In the second method, as a score-based perspective, final tables can be formed by considering the results of all plays about each team.
Definition 3
Each team in a tournament with an n team has an (n-1) game. In which case, it can lead to different modes for each team in getting the result. Regardless of no limit, and only concerning all the different possible modes, the issue can be expected set of final tables.
As shown in Table 4, the number of possible scenarios to produce the final tables in the Result-based and Score-based approaches is very high. In these approaches, there are situations in the tables that are illegal states and should be removed from the set of answers. Therefore, it is clear that producing all tables and searching and removing illegal tables from these collections is very time-consuming and difficult. However, using permutation theory and a structured method can help solve this problem. In the proposed method, an arrangement should be made to consider the order of points in the production of tables and not to use cases that violate the complete descending order of the tables. In this case, there is no need for a survey to find and remove incorrect tables from the set of answers. So, it significantly reduced the problem execution time.
Number of teams | Result-based | Score-based |
|---|---|---|
3 | 27 | 27 |
4 | 729 | 1,296 |
5 | 59,049 | 100,000 |
6 | 14,348,907 | 11,390,625 |
7 | 10,460,353,203 | 1,801,088,541 |
8 | 22,876,792,454,961 | 377,801,998,336 |
9 | 150,094,635,296,999,121 | 101,559,956,668,416 |
10 | 2,954,312,706,550,833,698,643 | 34,050,628,916,015,625 |
The WDL-based perspectives can generate final tables for n teams by using final tables of (n-1) teams. In this method, we begin with creating results tables of a tournament by two teams. The set of this case is simple:
$$\left\{\left(\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\end{array}\right),\left(\begin{array}{ccc}0& 1& 0\\ 0& 1& 0\end{array}\right)\right\}$$
The algorithm starts with two-team tables. Different scenarios for the new team are added to the first line at each stage, and its effects are applied to the other lines. So will create new tables. After creating new tables in each step, invalid tables must be separated from the set of valid tables, and work with valid tables must continue.
For Example
consider we want to add (1,0,1) to previous table .
First, we calculate all effects of result (1,0,1) as follow:
$$\left\{\left(\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\end{array}\right),\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\end{array}\right)\right\}$$
Then, by adding (1,0,1) to first row, applied effects into other lines, as follow:
$$\left\{\left(\begin{array}{ccc}1& 0& 1\\ 2& 0& 0\\ 0& 0& 2\end{array}\right),\left(\begin{array}{ccc}1& 0& 1\\ 1& 0& 1\\ 1& 0& 1\end{array}\right)\right\}$$
In this case, we have two new tables, but the first table is illegal (it is not sorted by score) and must be eliminated. Thus, only the second table is acceptable.
Definition 4
The WDL result of each team in a tournament can be one of the elements of set A, which is defined as follows:
$$A\left(n\right)=\left\{\right(w,d,l\left)\right|w,d,l\in \{0..n-1\},and,w+d+l=n-1\}$$
This set has \(\frac{n\text{*}(n-1)}{2}\) element.
According to the WDL-based method, for step k, we first create set A (k), then by adding any element from set A to each table of the previous step, we can generate new final tables for this step. Note that adding each new row to the previous table must apply the new row effect to the other rows. Different modes will produce different results. Therefore, each previous table with each new line may create several new tables, but we must check all the cases and remove the illegal tables.
Due to a football tournament, each team plays once against all other teams. For example, each team will compete with three other teams to get the final table similar to Table 1. Since there is only one match between two teams, the total number of games will equal six matches. As mentioned before, each team plays n-1 matches, which according to the number of teams, the total number of games will be equal to m = n * (n-1). The total number of games is m/2 because it is one match for two teams in common. These are given in Equations 2 and 3.
$$B\left(b\right)=n-1$$
2
$$m\left(n\right)=\frac{n}{2}B\left(n\right)=\frac{n\left(n-1\right)}{2}$$
3
where B(n) is the number of games for each team and m(n) is the total number of games in a tournament with n team.
Given that each game can have three types of results, the number of situations in a tournament equals C, which is expressed in Eq. 4.
$$\text{C}\left(\text{n}\right)={3}^{m\left(n\right)}={3}^{\frac{n\left(n-1\right)}{2}}$$
4
Here, the final tables are created from the perspective of only the results, and the number of goals of the games is not considered. So, the characteristics of the game results, WDL, should be considered.
In a tournament, each team has a certain number of wins, draws, and losses, which is always equal to the number of games, i.e., n-1.
$${P}_{i}\left(n\right)= {w}_{i}+{d}_{i}+{l}_{i}=n-1, 1\le i\le n$$
5
Each win has three points, the draw has one point, and a loss is without any points. Each team's score can be considered as Eq. 6 based on its WDL values.
$$Pt{s}_{i}=3{w}_{i}+{d}_{i}, 1\le i\le n$$
6
A team can gain different combinations of WDLs through a tournament. The number of these situations depends on the number of competitions and equals Eq. 7.
$$\left\{\begin{array}{c}f\left(0\right)=1 \\ f\left(n\right)=f\left(n-1\right)+n+1\end{array}\right.=\frac{\left(n+1\right)\left(n+2\right)}{2}=\left(\genfrac{}{}{0pt}{}{n+2}{2}\right)$$
7
For example, in a 4-team tournament, each team can score in 10 various forms as follows:
{300,210,201,120,111,102,030,021,012,003}
The first digit shows the number of wins, the second digit shows the number of draws, and the third digit shows the number of losses. For example, 201 represents two wins, one loss, and no draw.
The final table of the games is prepared based on the points earned by the teams. So, teams with higher scores should be placed in the higher rows of the table. Therefore, given that each team can score a maximum of 3*w points, there can be limits to the scores per row. The limitations discussed are expressed in Equations 8 and 9.
$$0\le Pt{s}_{1}\le 3n-3$$
8
$$0\le Pt{s}_{k-1}\le Pt{s}_{k}$$
9
In the following, using the characteristics and limitations of the problem, a method based on functional programming will be described. The method is implemented using the Haskell programming language.
In this section, the methodology of producing final tables is described step by step based on WDL. In a general outline, work begins with producing an initial final table. The initial final table is a table with the number of tournament teams lined up, and all rows have zero values for WDL. Then all possible and valid cases for the first row are calculated and added to the initial table. As each mode is added, a new table is created. Because the valid WDL modes for the first row are more than one, the number of final tables generated after adding the first-row modes will be more than one table. The same operation is repeated for all other rows of all existing tables, and each time new tables are generated. In the end, all of the generated tables can be considered as final tables. The general flowchart of the proposed method is shown in Fig. 1.
First, an initial blank table is created to design the final tables. The initial table is a table that has a row with the number of teams, and in each row, the values of all columns L, D, and W are zero. This table is passed to a function that calculates all possible states for the first row and creates a new table for each state that contains the possible states in the first row. By inserting each mode in the first row, its effects are applied in the next rows. For example, if the mode is equal to (2,0,1), the effect of this state in the next rows will be one win and two losses. Therefore, since it is unclear which rows win and which rows lose, each situation must create separate tables. Each table's order should not change during the operation so that the score of each row should be equal to or higher than the row. At the end of the first-row operation, the corresponding operation is performed in the same way for the next rows for each obtained table. After operating for the last row, all the resulting tables will answer the problem.
In the following, the sections that can be useful for solving the problem are stated, and then the implementation done with one of the functional programming languages is given.
Production of possible WDLs
Each team in a tournament can achieve one of three results: win, draw and lose. Regardless of the order of results, the number of each type of result can determine the team's overall result. Eq. 6 can easily obtain the points earned by each team. We can consider different approaches to obtain all possible scenarios from the results. The simplest approach can consıder all possible situations and select only the modes allowed in Eq. 5. List 2 shows the proper code for the first approach to this topic in the Haskell programming language.
|
Algorithm resultStates( n ): retList = [] For W = 0 to n-1: For D = 0 to n-1: For L = 0 to n-1: If W + D + L = = n-1: Add (W, D, L) to retList return retList |
| List 2. first version of resultStates algorithm for generating all possible result states of each team. |
The resultStates function in List 2 receives input as the number of teams and returns all possible result scenarios that one team can achieve against the other teams. According to the resultStates function to obtain \(\frac{n*(n-1)}{2}\) correct state, \((n-1{)}^{3}\) states are examined. By applying changes to the above function and considering the impact values of each section in subsequent sections, the function listed in List 3 can reduce the number of studies.
|
Algorithm resultStates( n ): retList = [] For W = 0 to n-1: For D = 0 to n-W-1: For L = 0 to n-W-D-1: If W + D + L = = n-1: Add (W, D, L) to retList return retList |
| List 3. modified version of resultStates algorithm for generating all possible result states of each team. |
The function expressed in List 3 examines fewer modes than the function expressed in List 2. The total number of states studied in this function equals Eq. 10.
$$1+3+6+10+15+\dots +\frac{n*\left(n+1\right)}{2}=\frac{n*(n+1)*(n+2)}{3!}$$
10
Of course, the solution from Greg Cooperberg's idea seems to be a better solution. In this solution, for w, all possible states (0 .. n-1) are selected, and for each w state (0..n-w-1) is considered for d, and the value of L can be calculated by relation (L = n - w - d -1). The Haskell code for this solution is given in List 4.
|
Algorithm resultStates( n ): retList = [] For W = 0 to n-1: For D = 0 to n-W-1: Add (W, D, n-W-d-1) to retList return retList |
| List 4. last version of resultStates algorithm for generating all possible result states of each team. |
In this case, the number of events equals the number of cases and is considered the optimal solution.
Generating a set of game results that can gain a WDL for a team.
The result of a game affects both teams. Therefore, the results of a tournament for one team in a particular situation affect other teams. This section examines all the effects of one team's situations on other teams. The effects will be in the form of tables, each row related to the game's result with a team.
A team must compete in w + d + l for a specific WDL. If the order of the teams is also important, Eq. 11 can obtain the number of possible modes to generate a particular WDL.
$${P}_{wdl}\left(T\right)=\frac{n!}{w!d!l!}=\frac{(W+D+L)!}{W!D!L!}$$
11
For example, three different permutations for the state (2,0,1) could be as follows:
$$\left\{\left(\begin{array}{c}(\text{1,0},0)\\ (\text{1,0},0)\\ (\text{0,0},1)\end{array}\right),\left(\begin{array}{c}(\text{1,0},0)\\ (\text{0,0},1)\\ (\text{1,0},0)\end{array}\right),\left(\begin{array}{c}(\text{0,0},1)\\ (\text{1,0},0)\\ (\text{1,0},0)\end{array}\right)\right\}$$
According to the example above, the possible scenarios are:
-
Win over the first and second teams and lose to the third team.
-
Win over the first and third teams and lose to the second team.
-
Win over the second and third teams and lose to the first team.
We can use the tree method to produce different compounds. The algorithm starts by creating a set of elements labeled W, D, L according to the problem values as the initial set. A tree is then created whose root is denoted by R and contains the initial set. Then, child nodes for each element of the set (only once per member, if any) are created, labeled with the corresponding element value. Each child node has its own parent set from which the value of the node element has been removed. The above operation is repeated for each new node created. This process continues until all the sets in the leaves are empty. For example, we can do the following to get all the compounds of state (2,1,1):
First, a set of elements is formed as {W, W, D, L} and by assigning it to the root, the corresponding tree is created. Due to all three modes in the initial set, three child nodes with labels w, d, and l are created, and appropriate sets are assigned. The corresponding tree can be seen in Fig. 2.
The proposed algorithm is implemented on sets of leaves, and suitable children are created for them. Relevant sets are also calculated for each leaf. Figure 3 shows the problem tree for the second level.
With the complete implementation of the algorithm, the final tree is created according to Fig. 4. In the final, all the leaves have empty sets.
After creating the tree, each path from the root to the tree's leaves is a permutation of the desired set. A set of all these paths will serve as the answer. In the example given, the set of permutations according to the tree in Fig. 4 is as follows:
{ (W,W,D,L), (W,W,L,D), (W,D,W,L), (W,D,L,W), (W,L,W,D), (W,L,D,W), (D,W,W,L), (D,W,L,W), (D,L,W,W), (L,W,W,D), (L,W,D,W), (L,D,W,W) }
This method is done in two stages of tree production and creating an answer set. The tree production stage consists of non-recursive and recursive components. List 5 shows these two sections.
|
A: non-recursive section: 1. Get the desired state and create an initial set named U. 2. Create root of a tree with the element of R-value and put it as CurNode. B: recursive section: 3. For all unrepeated members in the U as member A (if exist): 4. Create child nodes for node CurNode with value labels A. 5. Remove one element of A from U. 6. Assign the new node as the CurNode. 7. Call section B again. |
| List 5. The tree production stages, A: non-recursive section, B: recursive section. |
The generated tree is traversed in the production set of the response. The algorithm for this step is shown in List 6.
|
a) Gets the tree and perform the following steps for all child nodes: b) If the desired node doesn’t have any child, label value will be returned. c) Recall the algorithm with its child nodes and put back value on ‘S’. d) Add ‘S’ to the answer set. |
List 6. producing solution from tree
Implementing in Haskell
The method described in this research is based on functional programming. As one of the functional programming languages, Haskell can be used to implement the proposed method. The Haskell language is a set of functions, usually programming as recursive functions.
This section deals with implementing the proposed method using the Haskell language. Here, a need is to define a new structure as a recursive data structure. The proposed method presents the following tree data structure.
We can use the following process to create an empty table for n teams:
$$\left[\right(\text{0,0},0\left) \right| x \leftarrow [1 ... n]]$$
This function creates a list containing n topples with values (0,0,0).
The program starts with calling a function named findTables. This function has an input that specifies the number of tournament teams. The output of the finalTables function is the final table set, which is considered the answer to the problem. This function has been developed to implement the non-recursive part of the proposed method. The recursive part is implemented by a function called stage'. The finalTables function returns the results of the stage' function. Also, in the finalTables function, the stageN function is called. The initial table has been sent for this function, and the function applies all possible scenarios for the first row in the initial table. The tables created are passed from the stageN function to the stage' function. So, stage' is repeated for the second row to the end. Here the stageList function generates a list of all possible states for a specific row of tables. We will examine this function in a separate section. The Haskell code of described functions is as follows:
$$finalTables :: int \to \left[\left[Row\right]\right]$$
$$finalTables 0 = \left[\right[\left]\right]$$
$$finalTables n = stag{e}^{\text{'}} list1 n 1$$
$$where list1 = stageN\left(\left[\text{0,0},0\right]|x\leftarrow \left[1\cdots n\right]\right]) \left(stageList n 0 \left(n,\text{0,0}\right)\left(\text{0,0},0\right)\right) 1$$
$$stag{e}^{\text{'}} :: \left[\left[Row\right]\right]\to Int \to int \to \left[\left[Row\right]\right]$$
$$stag{e}^{\text{'}} \left[\right] \_ \_ = \left[\right]$$
$$stag{e}^{\text{'}} \left(xs:xss\right) n r = rmdups (tbls++(stag{e}^{\text{'}} xss n r)$$
$$where tbls = oneState xs n (r+ 1 )$$
$$oneState :: \left[Row\right] \to int\to Int \to \left[\left[Row\right]\right]$$
$$oneState xs n r$$
$$|r==n+1 = \left[xs\right]$$
$$| otherwise = stag{e}^{\text{'}} \left(stageN xs \left(stageList n r \left(xs‼\left(r-2\right)\right)\left(xs‼\left(r-1\right)\right)\right)r\right) n r$$
$$stageN :: \left[Row\right] \to \left[Row\right]\to Int \to \left[\left[Row\right]\right]$$
$$stageN \_ \left[\right] \_ = \left[\right]$$
$$stageN xs \left[\right(\text{0,0},0\left)\right] \_ = \left[xs\right]$$
$$stageN xs \left(y:ys\right) r = \left(add \left(r-1\right) xs \left(permutation y\right)\right)++stageN xs ys r$$
The functions listed above form the main body of the program. These functions implement the proposed method by calling each other. Table 5 shows the list of functions of the main part of the program with the necessary explanations.
|
Function Name |
Description |
Input Parameters |
Output |
|---|---|---|---|
|
finalTables |
The main function |
Number of teams |
Set of all final tables |
|
stage' |
Apply operations related to the method provided on all rows of the table. |
A set of tables, number of teams, and the desired row |
Final and intermediate tables |
|
oneState |
It is a stage's auxiliary function responsible for performing operations on a row. |
A table, number of teams, and desired row |
Modified table |
|
stageN |
It is responsible for adding a state to a row and applying its effects to other rows. |
A table to be added, Source tables, and desired row |
Modified table |
In the functions listed in Table 5, the permutation, stageList, and add functions are also used to obtain different combinations of results, a list of all possible scenarios that a team can achieve, and the addition of a table to another table, respectively.
The permutation function obtains a list of required tables by calling formTree and readTree functions. The formTree and readTree functions are also used to create and trace trees according to the content described in the previous section. The code list for creating combinations from the tree method is given below.
$$formTree :: \left[Row\right] \to \left[Tree\right]$$
$$formTree xs = map\left(\text{'}formNod{e}^{\text{'}}xs\right)\left(filter \left(\text{'}ele{m}^{\text{'}}xs\right)\right[\left(\text{1,0},0\right),\left(\text{0,1},0\right),\left(\text{0,0},1\right)]$$
$$formNode :: \left[Row\right] \to \left[Row\right]\to Int \to \left[\left[Row\right]\right]$$
$$formNode y xs$$
$$\left|length\right(xs)==1 = Node y []$$
$$| otherwise = Node y (formTree \left(xs \backslash \backslash \left[y\right]\right))$$
$$readTree :: \left[Tree\right] \to \left[\right[Row\left]\right]$$
$$readTree xs = foldr \left( \backslash x y \to readTre{e}^{\text{'}}x++y\right) \left[\right] xs$$
$$readTree\text{'} :: Tree \to \left[\right[Row\left]\right]$$
$$readTre{e}^{\text{'}} \left(Node x \left[\right]\right) =\left[\left[x\right]\right]$$
$$readTre{e}^{\text{'}} \left(Node x xs\right) = map\left(\backslash y \to \left[x\right]++y\right) \left(foldr\left(\backslash x y\to readTre{e}^{\text{'}} x++y\right) \right[\left] xs\right)$$
$$permutation :: Row \to \left[\left[Row\right]\right]$$
$$permutation \left(w,d,l\right) = map\left(\backslash xs \to \left(w,d,l\right):xs\right) \left(readTree \left(formTree \left(setEleman \left(l,d,w\right)\right)\right)\right)$$
$$where setEleman \left(w,d,l\right)= \left[\left(\text{1,0},0\right)|x\leftarrow \left[1..w\right]\right]++\left[\left(\text{0,1},0\right)|x\leftarrow \left[1..d\right]\right]++\left[\left(\text{0,0},1\right)|x\leftarrow \left[1..l\right]\right]$$
Another function used in the proposed program is the add function. This function is used to place a row of a table in the corresponding row of other tables and add the values of the other rows of a table to the corresponding values in other tables. The add function inserts the rth row of the table at the beginning of the tables returned from the addTb function. The addTb function adds the values of the two tables sent using an operator called (! +).
For example, suppose a tournament with four teams. For this tournament, in the first row, consider the probable state (1,0,2). According to the mentioned features, the effects of this state are equal to:
$$\left\{\left(\begin{array}{c}(\text{1,0},0)\\ (\text{1,0},0)\\ (\text{0,0},1)\end{array}\right),\left(\begin{array}{c}(\text{1,0},0)\\ (\text{0,0},1)\\ (\text{1,0},0)\end{array}\right),\left(\begin{array}{c}(\text{0,0},1)\\ (\text{1,0},0)\\ (\text{1,0},0)\end{array}\right)\right\}$$
So, this state can create the following tables from the initial blank table.
$$\left(\left(\begin{array}{c}(\text{2,0},1)\\ (\text{1,0},0)\\ (\text{1,0},0)\\ (\text{0,0},1)\end{array}\right),\left(\begin{array}{c}(\text{2,0},1)\\ (\text{1,0},0)\\ (\text{0,0},1)\\ (\text{1,0},0)\end{array}\right),\left(\begin{array}{c}(\text{2,0},1)\\ (\text{0,0},1)\\ (\text{1,0},0)\\ (\text{1,0},0)`\end{array}\right)\right)$$
The list of code for add and addTb functions is given below.
$$add :: Int \to \left[Row\right] \to \left[\left[Row\right]\right] \to \left[\left[Row\right]\right]$$
$$add r xs \left(yss\right) = \left[take r xs++addTb \left(drop r xs\right) ys \right| ys \leftarrow yss$$
$$addTb :: \left[Row\right] \to \left[Row\right] \to \left[Row\right]$$
$$addTb xs ys = \left[x !+y \right| \left(x, y\right)\leftarrow zip xs ys$$
$$where \left(!+\right) \left(w1,d1,l1\right) \left(w1,d1,l1\right) = (w1+w2, d1+d2, l1+l2)$$
Another function used in the proposed program is the stageList function. This function generates all possible states for a row. In this function, the values of the effects of the previous lines must be considered. So, we can create possible states according to the previous, and the current state can be subtracted. We should remove states with negative values from the list of states. As it turns out, this method of state generation may not be appropriate, as it produces invalid states. Generating and then deleting invalid states will increase the complexity of the program. The following is an efficient way to produce this type of case.
Improved production of possible states.
We can place limitations rules on generating possible states of a row to optimize the table production process. Restrictions should destroy the possibility of producing invalid states. Thus, we can improve the efficiency of this part of the algorithm.
In a tournament with n teams, one can win all of their games at best, i.e., status (n-1,0,0). This team will be the first team at the table. In the worst case, the first team can also happen (0, n-1,0). This situation happens when all the teams have achieved the same result. On the other hand, the team that loses all its games will be in the last row of the table as the worst possible situation, i.e. (0, 0, n-1). In the best case, this team can achieve the maximum result \(\left(⌊\frac{n-1}{2}⌋,(n-1)\%2,⌊\frac{n-1}{2}⌋\right)\)).
For example, in a four-team tournament, the first team can score (3,0,0) at best and (0,3,0) at worst. Also, the last team can get the result (0,3,0) in the best case and (0,0,3) in the worst case.
Now suppose the final table is divided into two pieces as follows:
$$\left(\begin{array}{c}1\\ 2\\ \begin{array}{c}⋮\\ k\\ ⋮\end{array}\\ n\end{array}\right)=\begin{array}{c}\left(\begin{array}{c}1\\ 2\\ \begin{array}{c}⋮\\ k\end{array}\end{array}\right)\\ \left(\begin{array}{c}k\\ ⋮\\ \begin{array}{c}⋮\\ n\end{array}\end{array}\right)\end{array}$$
Team k is the last team in the first part, and the first team is in the second part. Team k is the last team in the first part and is the first team in the second part. Minimum and maximum values can be obtained for team k. For this purpose, suppose \({P}_{1,max}^{k}\) and \({P}_{2,max}^{k}\) are the best states for the team k in the first and second sections, respectively. Also, \({P}_{1,min}^{k}\) and \({P}_{2,min}^{k}\) are the worst team k in the first and second parts. So, the following relationships are established:
$$\left\{\begin{array}{c}{P}_{1,max}^{k}=\left({W}_{1,max}^{k},{D}_{1,max}^{k},{L}_{1,max}^{k}\right) =(⌊\frac{k-1}{2}⌋, \left(k-1\right)\%2, ⌊\frac{k-1}{2}⌋\\ {P}_{1,min}^{k}=\left( {W}_{1,min}^{k},{ D}_{1,min}^{k},{ L}_{1,min}^{k}\right) =\left(0, 0, k-1\right) \\ \begin{array}{c}{P}_{2,max}^{k}=\left({W}_{2,max}^{k},{D}_{2,max}^{k},{L}_{2,max}^{k}\right) =\left(n-k, 0, 0\right) \\ {P}_{2,min}^{k}=\left({ W}_{2,min}^{k},{ D}_{2,min}^{k},{ L}_{2,min}^{k}\right) =\left(0, n-k, 0\right) \end{array}\end{array}\right.$$
12
Therefore, considering that team k has both the first part's characteristics and the second part's characteristics. We can consider the following relation:
$$\left\{\begin{array}{c}{P}_{max}^{k}={P}_{1,max}^{k}+{P}_{2,max}^{k}=(n-k+⌊\frac{k-1}{2}⌋, \left(k-1\right)\%2, ⌊\frac{k-1}{2}⌋)\\ {P}_{min}^{k}={P}_{1,min}^{k} +{ P}_{2,min}^{k}=\left(0, n-k, k-1\right) \end{array}\right.$$
13
The following relation can be obtained by considering relations 6 and 13:
$$n-k-1\le (3\times {W}_{k}+{D}_{k})\le 3\times \left(n-k+⌊\frac{k-1}{2}⌋\right)+ \left(k-1\right)\%2$$
14
Also, the following conditions can be considered in the production of possible states. Assuming (a, b, c) as the values of the (r-1)th row and (x, y, z) as the values of the rth row, we can use the following in the 'stageList' function.
We should correct Eq. 5 since (x, y, z) are the effects of the above row results.
$${P}_{r}\left(n\right)= {w}_{r}+{d}_{r}+{l}_{r}=n-\left(x+y+z\right)-1,$$
15
Values (W, D, L) must be selected from the following values:
$$\left\{\begin{array}{c}W\leftarrow \left[0 \cdots n-k-1\right] \\ D\leftarrow \left[0 \cdots n-W-y-1\right] \\ L\leftarrow [0 \cdots n-W-D-z-1]\end{array}\right.$$
16
Also, each row must have equal values or values less than the above row. Therefore, the following limitation must be added:
$$3\times \left(W+x\right)+D+y\le 3*a+b$$
17
According to the contents of this section, the stageList function can be developed as follows:
$$stageList :: Int \to Int \to Row \to Row \to \left[Row\right]$$
$$stageList n k \left(a,b,c\right) \left(x,y,z\right) = reverse\left[(w,d,l)\right| w\leftarrow \left[0..n-x-1\right], d\leftarrow \left[0..n-y-1\right], l\leftarrow \left[0..n-z-1\right],$$
$$w+d+l==n-\left(x+y+z\right)-1, 3*\left(w+x\right)+d+y<=3*a+b, 3* w+d>=n-k-1,$$
$$3*w+d<=(n-k+ div (k-1\left) 2\right)*3 + \left(mod \right(k-1\left) 2\right)]$$
This article focused on examining all the possible outcomes of games involved in football tournaments to produce all possible final tables. In this study, each team's number of wins, losses, and draws leads to the production of final tables. Examining all possible permutations can be used in the production of final tables. However, this method produces many invalid end tables. In this study, for each position in the final table, the possible result space is identified for the worst and best cases. By identifying the lower and upper limits of the results for each table row, we can significantly reduce the number of invalid states of the final tables.
- Raof, R. A., Sudin, S., Mahrom, N., & Rosli, A. C. (2018). Sport Tournament Automated Scheduling System. In MATEC Web of Conferences (Vol. 150, p. 05027). EDP Sciences.
- Dagaev, D., & Zubanov, A. (2017). Round-robin tournaments with limited resources. Higher School of Economics Research Paper No. WP BRP, 171.
- Toffolo, T. A., Christiaens, J., Spieksma, F. C., & Berghe, G. V. (2019). The sport teams grouping problem. Annals of Operations Research, 275(1), 223–243.
- Csató, L. (2021). Analysing the restricted assignment problem of the group draw in sports tournaments. arXiv preprint arXiv:2103.11353.
- Noll, R. G. (2003). The organization of sports leagues. Oxford Review of Economic Policy, 19(4), 530–551.
- Yi, X. (2021). Dealing with uncertainty in round robin sports scheduling (Doctoral dissertation, Springer Berlin Heidelberg).
- M.H. Eggar, A tournament problem, Discrete Mathematics 263 (2003) 281–288.
- M. Henz, T. Mu¨ ller, S. Thiel, Global constraints for round robin tournament scheduling, European Journal of Operational Research (EJORS) 153 (1) (2004) 92–101.
- J.W. Moon, Topics in Townaments, Holt, Rinehart and Winston. (1968).
- O’Donoghue, P. (2018). Tournaments. In Modelling and Simulation in Sport and Exercise (pp. 129–145). Routledge.
- K.B. Reid and L.W. Beineke, Tournaments, In Selected Topics in Graph Theory, (Edited by L.W. Beineke and R.J. Wilson), pp. 169–204, Academic Press, London, (1979).
- I.Anderson, Combinatorial Design and Tournaments, Oxford University Press, (1997)
- R. Hemasinha, "An algorithm to generate tournament score sequences", Mathematical and Computer Modelling 37 (2003) 377–382.
- S.V. Gervacio, Score sequences: Lexicographic enumeration and tournament construction, Discrete Mathematics 72, 151–155, (1988).
- T.V. Narayana, R.M. Mathsen and J. Sarangi, An algorithm for generating partitions and its applications J. Combinatorial Theory 11, 54–61, (1971).
- I. Charon, O. Hudry, A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments, Discrete Applied Mathematics 154 (2006) 2097–2116.
- Nabiyev, V. V., & Pehlivan, H. (2008). Tournament scoring problem. Applied mathematics and computation, 199(1), 211–222.
- Damkhi, M., & Pehlivan, H. (2018). Generation and Enumeration of Final Table States of Football Tournaments Using a Blind Adaptive Filtering Algorithm. International Journal of Computing, 7(2), 22–28.
- Milani, M., & Mwakondo, F. (2021). Particle Swarm Algorithm for Improved Handling of the Mirrored Traveling Tournament Problem. Tehnički vjesnik, 28(5), 1647–1653.
- Liang, Y. C., Lin, Y. Y., Chen, A. H. L., & Chen, W. S. (2021). Variable Neighborhood Search for Major League Baseball Scheduling Problem. Sustainability, 13(7), 4000.
- Csató, L. (2017). On the ranking of a Swiss system chess team tournament. Annals of Operations Research, 254(1), 17–36.
No competing interests reported.