\[c = \frac{e + r}{2 r - 1} \tag{1} \]
\[s = c r = \frac{r \left(e + r\right)}{2 r - 1} \tag{2} \]
I came across this problem while working on a method to generate a color palette consisting of \(n\), where all colors are visibly different from one another. I wanted compact way of visualizing the palette to see what colors are too close to each other, and which ones are far enough apart. One way would be to list all \(\frac{n*(n-1)}{2}\) pairs of colors, but that would be a long one-dimensional list. What I wanted instead is to visualize the colors in a grid that is guaranteed to have each pair of colors present somewhere as neighbors, and where no two neighbors are the same color. The second condition is of course necessary since we are trying to create a tool for comparing different colors by showing them as adjacent cells, and hence we want to make sure we are not repeating the color in two adjacent cells.
Problem Statement
The problem we are trying to solve can be stated as follows:
Given an integer \(n\), construct a grid where each cell contains an integers in \([0, n-1]\), such that,
- every possible pair of integers \((i,j)\), \(i \ne j\), \(i\), \(j\) in \([0, n-1]\) is present at least once as two horizontally or vertically adjacent cells in the grid, and,
- no two horizontally or vertically adjacent cells contain the same integer.
Note that \((i,j)\) is present \(\iff\) \((j,i)\) is also present, and hence they are essentially the same pair.
Ideally, the grid should be as small as possible. But let us not worry about that for now.
We know the grid cannot contain less than \(n\) cells, otherwise we would be missing some numbers; but that is too low of lower bound on the grid size. Let us see if we can find a lower bound higher than this.
A grid of size \(r \times c\) can represent at most \((r-1)c + (c-1)r\) pairs because that is the number of internal edges, each of which shared by two cells (and so, excluding edges on the outer border).
Further, we only need to consider square grids to find a lower bound. This follows from the claim that of all grid sizes containing the same number of internal edges, the smallest grid size, if size is measured by the number of cells, must have \(r=c\). The proof is as follows. If we call the number of internal edges \(e\), where \(e = (r-1)c + (c-1)r\) and the grid size \(s\), where \(s = rc\), then,
\[ \frac{\partial s}{\partial r} =\frac{- e + 2 r^{2} - 2 r}{\left(2 r - 1\right)^{2}} \tag{3} \]
Setting \(\frac{\partial s}{\partial r}=0\) we get:
\[r_{min} = \frac{\sqrt{2 e + 1}}{2} + \frac{1}{2} \tag{4} \]
Subsituting \(r_{min}\) from \((4)\) into \((1)\) we get:
\[c_{min} = \frac{2 e + \sqrt{2 e + 1} + 1}{2 \sqrt{2 e + 1}} = \frac{\sqrt{2 e + 1}}{2} + \frac{1}{2} = r_{min} \tag{5} \]
Hence, the square grid is an extremum. Note that the second derivative of \(s\) is:
\[ \frac{\partial^2 s}{\partial r^2}=\frac{2 \cdot \left(2 e + 1\right)}{\left(2 r - 1\right)^{3}} \tag{6} \]
Subsituting \(r_{min}\) from \((4)\) into \((6)\) we get:
\[\frac{\partial^2 s}{\partial r^2}(r_{min})=\frac{2}{\sqrt{2 e + 1}} \gt 0 \tag{7} \]
which is a positive constant and therefore, the square grid with \(r = c = r_{min} = c_{min}\) is where the grid size, \(s\), is minimum.
By setting \(e = \frac{n(n-1)}{2}\), which is the total number of pairs, and substituting in \((4)\), we can establish the a lower bound on the dimension \(d\), (\(r=c=d\)), of the grid:
\[ d \ge \frac{\sqrt{n \left(n - 1\right) + 1}}{2} + \frac{1}{2} \tag{8} \]
As a fraction of \(n\), this converges to:
\[ \lim_{n \to \infty}\left(\frac{\frac{\sqrt{n \left(n - 1\right) + 1}}{2} + \frac{1}{2}}{n}\right)=\frac{1}{2} \tag{9} \]
Therefore, the solution cannot be achieved with a grid size smaller than \(\frac{n}{2} \times \frac{n}{2}\). The optimum solution may of course be higher than this theoretical lower bound.
Solutions
I could not find much information about this problem except for a relevant stackoverflow question that did not seem to have received much attention. A solution among the answers proposed to start by placing a number in the corner and build the grid by adding numbers iteratively towards satisfying the constraints. This could be an interesting approach but I have not tried it yet.
A possible basic solution is to take the full list of pairs and arrange them in a grid. For example, the first row could contain the sequence of the following \(n-1\) pairs, which when arranged this way, will not have any number adjacent to itself: \[(\phantom{nnn}0,\phantom{nnn}1), (\phantom{nnn}0,2), (\phantom{nnn}0,3), \dotsc, (\phantom{nnn}0,n-2), (\phantom{nnn}0,n-1)\] Following this pattern, whose odd columns resemble a Toeplitz matrix, the remaining rows will contain \[(\phantom{nnn}1,\phantom{nnn}2), (\phantom{nnn}1,3), (\phantom{nnn}1,4), \dotsc, (\phantom{nnn}1,n-1), (\phantom{nnn}1,\phantom{nnn}0)\] \[(\phantom{nnn}2,\phantom{nnn}3), (\phantom{nnn}2,4), (\phantom{nnn}2,5), \dotsc, (\phantom{nnn}2,\phantom{nnn}0), (\phantom{nnn}2,\phantom{nnn}1)\] \[ \dotsc \] \[(n-2,n-1), (n-2,0), (n-2,1), \dotsc, (n-2,n-4), (n-2,n-3)\] \[(n-1,\phantom{nnn}0), (n-1,1), (n-1,2), \dotsc, (n-1,n-3), (n-1,n-2)\]
Since the \(i^{th}\) row contains all pairs that begin with \(i\), the \(n\) rows of the grid contain all possible pairs. In addition, because each column always contains an increasing sequence (modulo \(n\)) of numbers, there are no self-adjacent numbers vertically. Therefore, the grid satisfies the two conditions we wanted. The size of this grid is \(n \times 2(n-1)\).
Looking at this arrangement, and given that a pair \((a,b)\) is equivalent to a pair \((b,a)\), it is easy to observe that the pairs represented by last two columns are equivalent to the pairs represented by the first two columns, shifted cyclically down by one row. The same is true for the third and fourth to last columns, which are equivalent to the third and fourth columns shifted cyclically down by two rows, and so on. This means that we can reduce the size of the grid by about half, by only considering the first \(\lfloor \frac{p+1}{2} \rfloor\) pairs, where \(p=n-1\) is the number of pairs per row. Hence, the size of the grid can now be reduced to \(n \times 2\lfloor \frac{n}{2} \rfloor\).
It can also be shown that the first three columns can be removed if \(n>=6\). This is because the first two columns capture only \(k\) and \(k+1 \pmod n\) pairs, which are abundantly represented throughout the grid. Additionally, the pairs generated by the 3rd and 4th columns are the same pairs generated by the 4th and 5th. The size of the grid can now be reduced to \(n \times (2\lfloor \frac{n}{2} \rfloor - 3)\) if \(n>=6\).
Another possible solution is as follows. We will keep horizontal adjacency constant throughout and focus on vertical adjacency. We start with the sequence \(0,1,2,\dotsc,n-1\) as the first row. Then, in the second row, place a (cyclically) shifted by \(1\) version of the first row: \(n-1,0,1,2,\dotsc,n-2\). With this, each number is now below the number that is next to it in the sequence (e.g., \(0\) is under \(1\)). In the third row, place a (cyclically) shifted by \(2\) version of the second row (i.e., by \(3\) of the first row): \(n-3,n-2,n-1,0,1,\dotsc,n-4\). Now \(0\) is under \(2\). This way, with every new row, each number gets to be vertically adjacent to a new number (one number higher than what it was adjacent to in the previous row). The amount of shift in terms of the first row will be \(1,3,6,10,15,\dotsc\). Essentially, we have the sequence of all the numbers walking past the sequence of all the numbers and therefore each number gets to meet each other number, just like when the players of two teams line up and walk past each other to shake hands. Hence, we will call this solution the players handshake algorithm.
This pattern needs to stop before a number becomes vertically adjacent to itself, which would take \(n\) rows. But we can stop earlier. To see this, let us take a look at the full matrix of the grid with \(n=5\),
\[ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 \\ 4 & 0 & 1 & 2 & 3 \\ 2 & 3 & 4 & 0 & 1 \\ 4 & 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & 3 & 4 \end{bmatrix} \]
and with \(n=6\),
\[ \begin{bmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 5 & 0 & 1 & 2 & 3 & 4 \\ 3 & 4 & 5 & 0 & 1 & 2 \\ 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 4 & 5 & 0 & 1 & 2 \end{bmatrix} \]
In the second row of these matrices, we established \(n\) new vertical pairs, and in each subsequent row, another set of \(n\) new pairs are added. Since the total number of possible pairs is \(\frac{n(n-1)}{2}\), we should be able to stop after \(\frac{n-1}{2}\) rows. It can be seen in the above two matrices that the first two rows and the last two rows contain the same vertical pairs, and so on. When \(n=5\), we need 3 rows to get all the pairs, and when \(n=6\), we need 4 rows to get all the pairs. Hence, the number of rows needed is \(\lceil \frac{n+1}{2} \rceil\) (or \(\lfloor \frac{n}{2} \rfloor + 1\)). The size of the grid is now \(\lceil \frac{n+1}{2} \rceil \times n\), which is an improvement over the first solution, and only twice the size of the theoretical lower bound.
Finally, we can remove the first row because the vertical pairs it contributes by neighboring the second row are redundant as they are captured by the horizontal adjacency of the remaining rows. So the final size of the grid is \(\lfloor \frac{n}{2} \rfloor \times n\).
Code
Let us write a function to count the number of pairs that are adjacent to each other in a given grid.
import numpy as np
import numpy.typing as npt
import typing
def count_neighbors(a: npt.NDArray[np.int32], n: int) -> npt.NDArray[np.int32]:
"""Count the number of neighbors of each element in a.
Parameters
----------
a : np.ndarray[np.int32]
The array containing the labels which are integers in [0,n-1].
n : int
The number of labels.
Returns
-------
np.ndarray[np.int32]
A symmetric nxn matrix where element i,j counts how many times
labels i and j appear horizontally or vertically next to each
other in a.
"""
# Expecting the values to be in [0,n) or an empty array
assert a.size==0 or a.max()<n and a.min()>=0
counts = np.zeros((n,n), dtype=np.int32)
for i in np.arange(a.shape[0]):
for j in np.arange(a.shape[1]):
if i>0:
counts[a[i,j],a[i-1,j]]+=1
if i<a.shape[0]-1:
counts[a[i,j],a[i+1,j]]+=1
if j>0:
counts[a[i,j],a[i,j-1]]+=1
if j<a.shape[1]-1:
counts[a[i,j],a[i,j+1]]+=1
# Function correctness check. There are a.shape[0]-1 pairs per row and a.shape[1]-1
# pairs per column. So the total number of pairs is
num_pairs = (a.shape[0]-1)*a.shape[1]+(a.shape[1]-1)*a.shape[0] if a.size>0 else 0
# (The size check is because an empty array can have a shape of (1,0) for example)
# Each pair increments two (symmetric) entries in the counts matrix. Therefore,
assert counts.sum() == 2*num_pairs
return counts
def correct(counts: npt.NDArray[np.int32]) -> bool:
"""Check if the counts adjacency matrix satisfies the conditions of the problem.
Parameters
----------
counts : np.ndarray[np.int32]
A symmetric nxn matrix where element i,j counts how many times
labels i and j appear horizontally or vertically next to each
other in a.
Returns
-------
bool
True if the counts matrix satisfies the conditions of the problem.
"""
# set diagonal to 1 if diagonal in the original matrix is 0
counts2=np.copy(counts)
np.fill_diagonal(counts2,np.diag(counts)==0)
# if all elements are nonzero, then the matrix is correct
return np.all(counts2) Here is how we can generate the grid using the players handshake algorithm.
def players_handshake_grid(n: int) -> npt.NDArray[np.int32]:
if n==3: # degenerate case
# Same as general case below but don't skip first row
return np.array([np.roll(np.arange(n),i) for i in np.cumsum(range(n//2+1))])
# General case
# Fill each row with the sequence 0,1,...,n-1 shifted by 1,3,6,10,15,...
return np.array([np.roll(np.arange(n),i) for i in np.cumsum(range(1,n//2+1))]) The basic solution can be implemented as follows:
def basic_solution_grid(n: int) -> npt.NDArray[np.int32]:
a=np.empty((n,2*(n//2)),dtype=np.int32)
# fill each even column with the sequence 0,1,2,...,n-1
a[:,::2]=np.arange(n)[:,None]
# fill each odd column with the sequence 0,1,2,...,n-1 shifted by 1,2,...,n//2
a[:,1::2]=np.array([np.roll(np.arange(n),-i-1) for i in range(n//2)]).T
if n>=6:
a=a[:,3:] # remove first 3 columns
return aAn example of the grid generated by the players handshake algorithm for \(n=7\):
# Players handshake with n=7
n=7
a=players_handshake_grid(n)
disp_arrays_horiz((a,'grid'),(count_neighbors(a,n),'adjacency'))
assert correct(count_neighbors(a,n))\[\begin{matrix}\left[\begin{matrix}6 & 0 & 1 & 2 & 3 & 4 & 5\\4 & 5 & 6 & 0 & 1 & 2 & 3\\1 & 2 & 3 & 4 & 5 & 6 & 0\end{matrix}\right]& & &\left[\begin{matrix}0 & 2 & 1 & 1 & 1 & 1 & 3\\2 & 0 & 3 & 1 & 1 & 1 & 1\\1 & 3 & 0 & 3 & 1 & 1 & 1\\1 & 1 & 3 & 0 & 2 & 1 & 1\\1 & 1 & 1 & 2 & 0 & 3 & 1\\1 & 1 & 1 & 1 & 3 & 0 & 2\\3 & 1 & 1 & 1 & 1 & 2 & 0\end{matrix}\right]\\\text{grid}& & &\text{adjacency}\end{matrix}\]
The adjacency matrix shows that each element is adjacent to each other element between 1 and 3 times, and never adjacent to itself (zero diagonal). Here is the grid generated by the basic solution for the same \(n\):
# Basic solution with n=7
n=7
a=basic_solution_grid(n)
disp_arrays_horiz((a,'grid'),(count_neighbors(a,n),'adjacency'))
assert correct(count_neighbors(a,n))\[\begin{matrix}\left[\begin{matrix}2 & 0 & 3\\3 & 1 & 4\\4 & 2 & 5\\5 & 3 & 6\\6 & 4 & 0\\0 & 5 & 1\\1 & 6 & 2\end{matrix}\right]& & &\left[\begin{matrix}0 & 3 & 1 & 1 & 1 & 1 & 2\\3 & 0 & 2 & 1 & 1 & 1 & 1\\1 & 2 & 0 & 2 & 1 & 1 & 1\\1 & 1 & 2 & 0 & 3 & 1 & 1\\1 & 1 & 1 & 3 & 0 & 3 & 1\\1 & 1 & 1 & 1 & 3 & 0 & 3\\2 & 1 & 1 & 1 & 1 & 3 & 0\end{matrix}\right]\\\text{grid}& & &\text{adjacency}\end{matrix}\]
We can verify correctness for a any number of examples and also check if the grid is the tightest it can be:
def check_tightness(a: npt.NDArray[np.int32], n: int) -> bool:
"""Check if the solution is tight by removing the first and last row and column.
Parameters
----------
a : np.ndarray[np.int32]
The solution.
n : number of labels.
Returns
-------
bool
True if none of the boundary rows or columns can be removed while maintaining
solution correctness.
"""
tight = True
if a.size>0 and correct(count_neighbors(a[1:,:],n)):
print(f'redundant first row for {n=}')
tight = False
if a.size>0 and correct(count_neighbors(a[:,1:],n)):
print(f'redundant first col for {n=}')
tight = False
if a.size>0 and correct(count_neighbors(a[:-1,:],n)):
print(f'redundant last row for {n=}')
tight = False
if a.size>0 and correct(count_neighbors(a[:,:-1],n)):
print(f'redundant last col for {n=}')
tight = False
return tight
def verify_method(n: int, method: typing.Callable[[int], npt.NDArray[np.int32]]) -> None:
"""Verify that the method returns a correct solution for n.
Parameters
----------
n : int
The number of players.
method : Callable[[int], np.ndarray[np.int32]]
The method to be tested.
"""
a=method(n)
assert correct(count_neighbors(a,n)), (n, a)
check_tightness(a,n)Applything this to the first 200 values of \(n\) using the players handshake algorithm, we get the following:
for n in range(200):
verify_method(n, players_handshake_grid)redundant first col for n=4
redundant last col for n=4Similarly, applying this to the first 200 values of \(n\) using the basic solution, we get the following:
for n in range(200):
verify_method(n, basic_solution_grid)redundant first row for n=2
redundant first col for n=2
redundant last row for n=2
redundant last col for n=2
redundant first row for n=4
redundant first col for n=4
redundant last row for n=4
redundant first col for n=5It is possible to show that the players handshake algorithm is not optimal in terms of grid size. For example, for \(n=10\), the algorithm generates a grid of size \(5 \times 10\):
disp_arrays_horiz(
(players_handshake_grid(10), 'players handshake grid $n=10$'),
(count_neighbors(players_handshake_grid(10),10), 'adjacency matrix'))
assert correct(count_neighbors(players_handshake_grid(10),10))
assert check_tightness(players_handshake_grid(10),10)\[\begin{matrix}\left[\begin{matrix}9 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\7 & 8 & 9 & 0 & 1 & 2 & 3 & 4 & 5 & 6\\4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3\\0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3 & 4\end{matrix}\right]& & &\left[\begin{matrix}0 & 5 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 4\\5 & 0 & 5 & 1 & 1 & 1 & 2 & 1 & 1 & 1\\1 & 5 & 0 & 5 & 1 & 1 & 1 & 2 & 1 & 1\\1 & 1 & 5 & 0 & 4 & 1 & 1 & 1 & 2 & 1\\1 & 1 & 1 & 4 & 0 & 4 & 1 & 1 & 1 & 2\\2 & 1 & 1 & 1 & 4 & 0 & 5 & 1 & 1 & 1\\1 & 2 & 1 & 1 & 1 & 5 & 0 & 4 & 1 & 1\\1 & 1 & 2 & 1 & 1 & 1 & 4 & 0 & 5 & 1\\1 & 1 & 1 & 2 & 1 & 1 & 1 & 5 & 0 & 4\\4 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 4 & 0\end{matrix}\right]\\\text{players handshake grid $n=10$}& & &\text{adjacency matrix}\end{matrix}\]
But here is a grid of size \(5 \times 8\) that is also a solution:
\[\begin{matrix}\left[\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\3 & 5 & 7 & 9 & 0 & 2 & 4 & 6\\7 & 0 & 4 & 8 & 1 & 5 & 9 & 2\\4 & 1 & 9 & 6 & 3 & 0 & 8 & 5\\9 & 3 & 8 & 2 & 7 & 1 & 6 & 0\end{matrix}\right]& & &\left[\begin{matrix}0 & 3 & 1 & 1 & 1 & 4 & 1 & 1 & 1 & 1\\3 & 0 & 1 & 3 & 1 & 1 & 1 & 1 & 1 & 1\\1 & 1 & 0 & 1 & 1 & 3 & 3 & 1 & 1 & 1\\1 & 3 & 1 & 0 & 1 & 1 & 1 & 3 & 1 & 1\\1 & 1 & 1 & 1 & 0 & 1 & 1 & 3 & 1 & 4\\4 & 1 & 3 & 1 & 1 & 0 & 1 & 1 & 1 & 1\\1 & 1 & 3 & 1 & 1 & 1 & 0 & 1 & 3 & 1\\1 & 1 & 1 & 3 & 3 & 1 & 1 & 0 & 1 & 1\\1 & 1 & 1 & 1 & 1 & 1 & 3 & 1 & 0 & 3\\1 & 1 & 1 & 1 & 4 & 1 & 1 & 1 & 3 & 0\end{matrix}\right]\\\text{a solution grid for $n=10$}& & &\text{adjacency matrix}\end{matrix}\]
The solutions I’ve shown here have a simple implementation and, especially the players handshake, is what I need for the original problem I was trying to solve: Distinct-color palette visualization. The other goal I had was to see how flexible and convenient it is to use the tools I used to create this post. I think I’ve achieved both goals. I hope you enjoyed reading this post as much as I enjoyed writing it. If you have any questions or suggestions, please leave a comment below. Thanks for reading!