# Round-robin Tournament Methodology (Mahjong)

Once I observed a method to generate a so-called perfect circulation on Sina blog.


Well it's too annoying to read mathematical expression in chinese, I brought it to English.

For $n=4^k$, construct a linear space $F_4^k$ with finite field $F_4$.
There are $4^k=n$ points in total inside $F_4^k$.
Consider a set $\{\vec{x}|\vec{x}=\vec{x_0}+\lambda\vec{h};\vec{x_0},\vec{h}\in F_4^k, \lambda \in F_4\}=L\subseteq F_4^k$.
There are 4 points lying on every lines.
By the properties of straight lines in vector space, there exists a unique straight line passing through two points.
Therefore, by seeing participants as points in the space, if 4 participants lying on the same straight line, then they have to compete to each other.
This is the desired perfect circulation.

## Pre-requisites
**Finite Field**
*Definition: A **finite field** is a field with finite elements.*
**Finite**
*Definition: Finite means countable.*
**Field**
*Definition: A group $(G,+,\cdot)$ satisfying the following field properties is called a **field**.*
- (A1): $a+b=b+a,\ \forall a,b \in F$
- (A2): $(a+b)+c=a+(b+c),\ \forall a,b,c \in F$
- (A3): $\exists 0 \in F$ s.t. $\forall x \in F, x+0=x=0+x$
- (A4): $\forall x \in F, \exists (-x) \in F$ s.t. $x+(-x)=0=(-x)+x$
- (M1): $ab=ba,\ \forall a,b \in F$
- (M2): $(ab)c=a(bc),\ \forall a,b,c\in F$
- (M3): $\exists 1 \in F$ s.t. $\forall x \in F, x\cdot 1=x=1 \cdot x$
- (M4): $\forall x \in F\setminus\{0\}, \exists x^{-1}\in F$ s.t. $x\cdot x^{-1}=1=x^{-1}\cdot x$
- (D1): $a(b+c)=ab+ac,\ \forall a,b,c\in F$
- (D2): $(a+b)c=ac+bc,\ \forall a,b,c\in F$

**Group**
*Definition: A group is a set equipped with binary operation $\circ$ satisfying:*
- Closure: if $a,b\in S$, then $\circ(a,b) \in S$
- Identity: $\exists e \in S$ s.t. $a\in S \implies \circ(a,e)=a=\circ(e,a)$
- Inverse: $\forall a \in S, \exists b \in S$ s.t. $\circ(a,b)=e=\circ(b,a)$

**Linear space(Vector space)**
*Definition: A space containing vectors that satisfying the following properties:*
- (A1): $u + (v + w) = (u + v) + w$
- (A2): $u + v = v + u$
- (A3): $\exists 0 \in V$ s.t. $\forall v \in V, v+0=v=0+v$
- (A4): $\forall v \in V, \exists −v \in V$ s.t. $v + (−v) = 0 = (-v) + v$.
- (M1): $a(b\vec{v}) = (ab)\vec{v}$
- (M2): $\exists 1 \in F$ s.t. $1\cdot\vec{v} = \vec{v}$
- (D1): $a(\vec{u} + \vec{v}) = a\vec{u} + a\vec{v}$
- (D2): $(a + b)\vec{v} = a\vec{v} + b\vec{v}$

**Polynomial Ring**
*Definition: A polynomial ring is denoted by $R[x]$, where $R$ is a ring, and elements in $R[x]$ is in the form of $$R+Rx+Rx^2+\cdots$$*

**Quotient Ring**
*Definition: A quotient ring is some polynomial ring over some expressions, which usually the elements of the ring itself, i.e. $R[x]/(f), f \in R$. In particular, when $f$ is irreducible (**prime** when in $\mathbb{N}$), denote an irreducible $f$ by $p$, such $R[x]/(p)$ is a finite field.*

## Desired $F_4$

The desired $F_4$ is $\mathbb{Z}_2[x]/(x^2+x+1)$.

Additive closure:

|+|0|1|x|x+1|
| --- | --- | ---- | ---- | ---- |
|**0**|0|1|x|x+1|
|**1**|1|0|x+1|x|
|**x**|x|x+1|0|1|
|**x+1**|x+1|x|1|0|

Multiplicative closure:

|$\times$|0|1|x|x+1|
| --- | --- | ---- | ---- | ---- |
|**0**|0|0|0|0|
|**1**|0|1|x|x+1|
|**x**|0|x|x+1|1|
|**x+1**|0|x+1|1|x|

In particular, we will set $x=2$ when computing participant index.

## Application of the method
We can now consider $64=4^3$ participants in the competition.
Then the linear space to be considered is $F_4^3$.
Set the position of the n-th participant to be $x_n=x_{1+z_1+4z_2+4^2z_3}=(z_1,z_2,z_3)$
Let's find out who will match with $x_1=(0,0,0)$.
In direction $(1,0,0)$:
- $x_1+1\cdot(1,0,0)=x_2$
- $x_1+x\cdot(1,0,0)=x_3$
- $x_1+(x+1)\cdot(1,0,0)=x_4$

Then the first match for p1 is with p2, p3, and p4.
How about the second match?
We see p1 hasn't match with p5, then

- $x_1+1\cdot(0,1,0)=x_5$
- $x_1+x\cdot(0,1,0)=x_9$
- $x_1+(x+1)\cdot(0,1,0)=x_{13}$

Again, for p1's third match:

- $x_1+1\cdot(1,1,0)=x_6$
- $x_1+x\cdot(1,1,0)=x_{11}$
- $x_1+(x+1)\cdot(1,1,0)=x_{16}$

What if we look for p1 and p6's match from p6's direction?

- $x_6+1\cdot(1,1,0)=x_{11}$
- $x_6+x\cdot(1,1,0)=x_{16}$
- $x_6+(x+1)\cdot(1,1,0)=x_1$

We can see the matchup is uniquely existed.

In fact, we can find out the matchups in one round by inputting only one vector $\vec{h}$ in calculation.

The respective result of 64 people is in the original post by [Lucas_Li_164439](http://blog.sina.cn/dpool/blog/s/blog_62b496ac01012fym.html).

## Coding

The following is the code available for generating such circulation.

SageMath version

import itertools 

F = GF(2**2, 'x', modulus=x**2+x+1)
hs = [[i for i in F] for _ in range(3)]

rounds_list = []

for hfs in list(itertools.product(*hs))[1:]:
    v = vector(F, hfs)
    round_list = []
    for x0fs in itertools.product(*hs):
        x0 = vector(x0fs)
        output_list = []
        for x in F:
            out = x0 + x*v
            participant = sum([(4**i)*e.polynomial().change_ring(ZZ).subs(x=2) for i, e in enumerate(out)]) + 1
            output_list.append(participant)
        output_list.sort()
        if not(tuple(output_list) in round_list):
            round_list.append(tuple(output_list))
    round_list.sort()
    if not(round_list in rounds_list):
        rounds_list.append(round_list)
        
for r in rounds_list:
    for i in r:
        print(i)
    print()

## Generalisation

We can consider perfect circulation over p-people matchup by $n=p^k$ and thus the expected linear space is $F_p^k$.
With the scope described above, we should consider all vectors over $F_p^k$. The process is massive, but we can still give the vector as below: $$\vec{h}=(F_p,F_p,F_p,\dots,F_p)\in F_p^k$$
To calculate the position vector of the n-th participants, we have to consider when $n=1$, position vector is $(0,0,\dots,0)$.
In fact, we can claim that if position vector is $(z_1,z_2,\dots,z_k)$, $n=1+z_1+pz_2+\dots+p^{k-1}z_k$.
This time, we should consider pointer for substitution:
<font color="#f00"> If we consider $F_{18}$, it doesn't make any sense to do substitution since $F_{18}=F_9 \times F_2$ is the only field expression. The result is not a single number and hence the program will become more complicated as we think, which is not suggested to do in programming.</font>
A so-called pointer is just the set $$P_k=\{0,1,2,\dots,k-1\}$$
We can make use of pointer to do substitution in programming.
Sagemath Code:

import itertools

p, k = 4, 2 %you can change them to suitable values.

F = GF(p, 'x')
hs = [[i for i in F] for _ in range(k)]
sub_x = factor(p)[0][0]

rounds_list = []

for hfs in list(itertools.product(*hs))[1:]:
    v = vector(F, hfs)
    round_list = []
    for x0fs in itertools.product(*hs):
        x0 = vector(x0fs)
        match = []
        for x in F:
            out = x0 + x*v
            participant = sum([(p**i)*e.polynomial().change_ring(ZZ).subs(x=sub_x) for i, e in enumerate(out)]) + 1
            match.append(participant)
        match.sort()
        if not(match in round_list):
            round_list.append(match)
    round_list.sort()
    if not(round_list in rounds_list):
        rounds_list.append(round_list)

for r in rounds_list:
    for i in r:
        print(i)
    print()

## Restriction to the methodology/program
The base $p$ must be any power of prime numbers, but not composite of prime powers. For example, $F_{16}$ is applicable in this method but $F_{18}$ is not due to the restriction of finite field.
The related research should focus on this way(?)
Well, things are stucked here. Of course, we can prevent from this type of error on our own.
## Non-perfect case
If the given total number of participants is not any perfect powers, we cannot do such pefect division.
However, we can find the closest $p^k$ to find out the optimized case, which is going to facing twice or more between players.
Suppose we now have 28 people to play mahjong, they need to have **equal** facing time to all other players. Then we will group them into group of 7, which gives $49=7^2$ is the closest suitable number for us to generate circulation.
Then each group got 7, and they will have a sub-tournament in the group. In this case, they will have 7 games in the subgroup and each player plays 4 times.

If there is any essays writing about it, please feel free to correct me and comment the reference. I will write the true solution to it.

## Special thanks
Programming: hoifanrd