Vtyjkyuk

I have $n$ people seated around a circular table, initially in arbitrary order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every person has sat either to the right or to the left of everyone else?

To be specific, we consider two different cases:

1. You can only switch people who are sitting next to each other.


2. You can switch any two people, no matter where they are on the table.

The small cases are relatively simple: if we denote the answer in case 1 and 2 for a given value of $n$ as $f(n)$ and $g(n)$ respectively, then we have $f(x)=g(x)=0$ for $x=1, 2, 3$, $f(4)=g(4)=1$. I'm not sure how I would generalize to larger values, though.

(I initially claimed that $f(5)=g(5)=2$, but corrected it based on @Ryan's comment).

If you're interested, this question came up in a conversation with my friends when we were trying to figure out the best way for a large party of people during dinner to all get to know each other.

Edit: The table below compares the current best known value for case 2, $g(n)$, to the theoretical lower bound $lceilfrac18n(n-3)rceil$ for a range of values of $n$. Solutions up to $n=14$ are known to be optimal, in large part due to the work of Andrew Szymczak and PeterKošinár.

beginarray r
hline
n & textBest known value of g(n) & leftlceilfrac18n(n-3)rightrceil & textComments\
hline
4 & 1 & 1 & \
hline
5 & 3 & 2 & \
hline
6 & 4 & 3 & \
hline
7 & 4 & 4 & \
hline
8 & 6 & 5 & \
hline
9 & 8 & 7 & \
hline
10 & 10 & 9 & \
hline
11 & 12 & 11 & \
hline
12 & 14 & 14 & \
hline
13 & 17 & 17 & \
hline
14 & 20 & 20 & \
hline
15 & 24 & 23 & \
hline
16 & 28 & 26 & \
hline
17 & 32 & 30 & \
hline
18 & 37 & 34 & \
hline
20 & 47 & 43 & textLoose upper bound\
hline
25 & 77 & 69 & textLoose upper bound\
hline
30 & 114 & 102 & textLoose upper bound\
hline
endarray

The moves corresponding to the current best value are found below. Each ordered pair $(i, j)$ indicates that we switch the people in seats $(i, j)$ with each other, with the seats being labeled from $1 ldots n$ consecutively around the table.

4 - ((2,1))
5 - ((2,5),(1,5),(1,3))
6 - ((5,3),(1,5),(2,5),(3,6))
7 - ((4,7),(3,7),(1,5),(2,5))
8 - ((1,2),(4,7),(1,5),(3,7),(1,6),(2,5)) (h.t. PeterKošinár)
9 - ((3,8),(1,4),(6,9),(4,8),(1,6),(5,8),(2,8),(2,9))
10 - ((3,8),(4,8),(7,10),(1,7),(3,6),(1,5),(2,9),(3,7),(1,4),(3,9))
11 - ((4,8),(2,9),(5,8),(1,7),(3,9),(7,11),(5,10),(1,4),(5,9),(2,7),(2,6),(5,10))
12 - ((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))
13 - ((1,2),(1,7),(3,9),(6,12),(8,11),(8,12),(1,11),(4,12),(9,12),(6,10),(7,10),(1,6),(2,8),(5,9),(3,8),(8,12),(9,12))
14 - ((1,4),(1,5),(1,8),(1,12),(4,11),(4,12),(9,13),(1,12),(9,12),(6,10),(6,9),(1,9),(4,7),(4,13),(3,13),(3,10),(2,13),(2,7),(3,13),(4,12))
15 - ((0,3),(0,10),(4,7),(2,8),(1,8),(5,9),(3,14),(5,13),(2,11),(4,9),(5,14),(4,12),(2,6),(7,14),(0,3),(2,9),(6,10),(8,11),(0,12),(0,4),(0,7),(3,7),(3,10),(2,13))
16 - ((10,14),(10,13),(0,10),(5,9),(5,8),(2,12),(2,5),(7,12),(2,12),(3,14),(5,11),(0,5),(4,14),(4,7),(3,11),(3,10),(0,8),(0,9),(0,6),(3,6),(1,14),(11,15),(1,5),(6,14),(3,11),(11,14),(0,12),(1,4))
17 - ((9,15),(5,13),(13,16),(0,13),(2,10),(10,16),(5,16),(5,13),(2,6),(2,10),(10,16),(7,10),(4,15),(1,8),(4,9),(5,12),(4,10),(3,13),(5,14),(1,4),(5,15),(1,6),(5,12),(8,12),(7,12),(4,12),(0,12),(8,11),(8,14),(7,16),(2,3),(1,8))
18 - ((4,7),(4,14),(6,10),(7,13),(4,7),(8,16),(8,13),(7,13),(3,8),(0,8),(4,8),(6,16),(1,12),(1,5),(5,11),(0,5),(14,17),(1,13),(8,13),(3,13),(0,4),(11,16),(2,10),(11,17),(9,15),(10,15),(1,9),(2,13),(1,4),(5,12),(6,14),(7,16),(13,17),(0,15),(1,15),(6,10),(5,15))
# Note that some solutions are zero-indexed and some are one-indexed.

The code I used to generate my the results can be found on Github. Unless otherwise specified, the switches above were found by my code, using a randomized greedy approach. As demonstrated by PeterKošinár, since the total number of possibilities is large, this approach may not find the best result even after many trials.

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 tfracn2 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)]

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