I have three integers representing positions on a board. Because all pieces are equal, the order does not matter, so it suffices to only consider increasing lists of three integers.
However I am having trouble finding a constant-time expression that encodes three integers in [0, n) as one integer with minimal range.
For two integers this formula would work. How can I generalize it?
$$a * n + b - \frac{a*(a+1)}{2}$$
Another problem that seems almost equivalent is how I can rotate and mirror the playing field to eliminate duplicate positions.
I have tried to find information on the internet about problems like these. Is there a name for them?
The formula that maps the triples of increasing numbers $0\le x <y<z<n$ to the set of numbers from $0$ to $\frac{1}{6}n(n-1)(n-2)-1$ is the following:
$$ \frac{x^3}{6}-\left(\frac{n}{2}-1\right)x^2+\left(\frac{(n-2)^2}{2}-\frac{1}{6}\right)x-\frac{y^2}{2}+\frac{2n-3}{2}y+z-n $$
For example, for $n=6$, we have $$ \begin{array}{ccc|c} x & y & z & f(x,y,z)\\\hline 0 & 1 & 2 & 0 \\ 0 & 1 & 3 & 1 \\ 0 & 1 & 4 & 2 \\ 0 & 1 & 5 & 3 \\ 0 & 2 & 3 & 4 \\ 0 & 2 & 4 & 5 \\ 0 & 2 & 5 & 6 \\ 0 & 3 & 4 & 7 \\ 0 & 3 & 5 & 8 \\ 0 & 4 & 5 & 9 \\ 1 & 2 & 3 & 10 \\ 1 & 2 & 4 & 11 \\ 1 & 2 & 5 & 12 \\ 1 & 3 & 4 & 13 \\ 1 & 3 & 5 & 14 \\ 1 & 4 & 5 & 15 \\ 2 & 3 & 4 & 16 \\ 2 & 3 & 5 & 17 \\ 2 & 4 & 5 & 18 \\ 3 & 4 & 5 & 19 \\ \end{array} $$ where $$ f(x,y,z)=\frac{x^3}{6}-2x^2+\frac{47}{6}x-\frac{1}{2}y^2+\frac{9}{2}y+z-6. $$
If the requirement is that the numbers are not-decreasing, i.e. $ 0\le x\le y \le z<n$, then the function that associates univocally a triple $(x,y,z)$ to a number in the from $0$ to $n (n + 1) (n + 2)/6-1$ is the following $$ \frac{x^3-3nx^2+(3n^2-1)x-3y^2+(3n-3)y}{6}+z $$