Making Friends around a Circular Table

Solution 1:

I didn't want to keep adding more and more comments, so I'll just post all my thoughts here. @PeterKošinár @VincentTjeng

States are only different if their underlying friend-graphs are non-isomorphic -- permuting the people-labels (or seat-labels) does not change the state you're in. You can drastically reduce your search space this way. For n=8 there are only ~3000 states within 6 swaps of the starting position. As an example, consider the very first swap. There are really only $\lfloor \tfrac{n}{2} \rfloor$ different swaps to make.

The problem is coming up with a canonical-representation for graphs. Fortunately, to reduce your state space you don't need a truly canonical representation. You only need to make sure you don't equate two non-isomorphic graphs. It's okay if isomorphic $A \sim B$ have different representations - it just means your search space has a few redundancies. In any case, I've written my own method in Python because I couldn't get any packages to work (I'll post it once I clean it up). A port to C with nauty would speed up the algorithm by a factor of 200+.

One naive canonicalization method is to permute the graph in all $n!$ ways and take the one that results in the lexicographically smallest adjacency list (using the binary sequence '001100....' as your representation). I use the same method, but I have a way to limit the number of valid permutations (down from $n!$ to ~$n^2$ on average). For example, since isomorphic graphs have the same degree sequence, we can enforce that the nodes are labelled by increasing order of degree. This by itself leads to a fairly drastic reduction of valid permutations. My idea iterates on that and is similar to finding the coarsest equitable partition that is described in this paper. The paper's algorithm (implemented by nauty) then goes on to do other stuff that I don't do, namely creating a search tree.

My exhaustive search algorithm begins in the starting position and runs a breadth-first-search of the state-space. I process a single state by making all possible swaps and then converting the resulting states to canonical form. The $i$th step of the algorithm takes $D_i \rightarrow D_{i+1}$ where $D_i$ is the set of all states that are at a distance $i$ from the starting position. The algorithm terminates once the final state has been found (complete-graph $K_n$). Of course, an exhaustive search will no longer be tractable for $n>12$, but you can easily turn it into a monte-carlo-type method.

For $n=10..12$ the search space becomes too large to store in memory. So I combine my BFS with @PeterKošinár's memoryless DFS method. I run the BFS for the first 4 swaps and then run a DFS starting from each state in $D_4$ (without keeping track of visited states). In the DFS we only make moves that add atleast 1 friend, and we prune states that can not possible beat the best solution found. We can make a max number of 8 friends per swap (counting duplicates (i,j) and (j,i)). So if we are in a state of $s$ swaps and $e$ friends, and we've found a solution with $s^*$ swaps, then we can prune if $s + \lceil (n^2 - e)/8 \rceil \geq s^*$.
$n=14$ distinct 4-swap sequences
$n=15$ distinct 4-swap sequences

I've run an exhaustive search for n=4..12 and can confirm the bounds we found as the true lower bounds. Here are the lexicographically smallest solutions (indices refer to seat-swaps).

• 4 $\quad$ - $\quad$ 1.[(1,2)]
• 5 $\quad$ - $\quad$ 3.[(1,2) (1,3) (1,4)]
• 6 $\quad$ - $\quad$ 4.[(1,2) (1,3) (1,5) (1,4)]
• 7 $\quad$ - $\quad$ 4.[(1,4) (1,5) (3,6) (2,6)]
• 8 $\quad$ - $\quad$ 6.[(1,2) (4,7) (1,5) (3,7) (1,6) (2,5)]
• 9 $\quad$ - $\quad$ 8.[(1,4) (1,5) (1,7) (1,6) (3,8) (2,8) (3,6) (1,5)]
• 10 $\quad$ - $\quad$ 10.[(1,2) (1,5) (1,6) (3,8) (4,10) (3,7) (5,8) (3,9) (3,10) (1,6)]
• 11 $\quad$ - $\quad$ 12.[(1,2) (1,4) (3,7) (6,9) (6,10) (1,5) (2,7) (3,11) (4,9) (4,8) (6,10) (4,11)]
• 12 $\quad$ - $\quad$ 14.[(1,2) (5,10) (1,6) (4,10) (1,7) (8,11) (4,12) (3,12) (1,9) (1,5) (7,11) (1,8) (5,10) (2,6)]

Solution 2:

Not an answer, but a toy to play with https://jsfiddle.net/zn1f30mv/14/embedded/result/