122
$\begingroup$

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 $\lceil{\frac{1}{8}n(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.

\begin{array} {|r|r|l|} \hline n & \text{Best known value of g(n)} & \left\lceil{\frac{1}{8}n(n-3)}\right\rceil & \text{Comments}\\ \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 & \text{Loose upper bound}\\ \hline 25 & 77 & 69 & \text{Loose upper bound}\\ \hline 30 & 114 & 102 & \text{Loose upper bound}\\ \hline \end{array}

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.

$\endgroup$
44
  • 5
    $\begingroup$ Can you provide the 'switches' that result in $f(5)=2$? The best I can get using your rules is $f(5)=3$. $\endgroup$
    – Ryan
    Jun 14, 2014 at 4:15
  • 4
    $\begingroup$ Well, $f(n)\ge\tfrac14n(n-3)$ and $g(n)\ge\tfrac18n(n-3)$, so $f(5)$ is definitely $3$, and it's not hard to show $g(5)=3$ also. $\endgroup$ Jun 14, 2014 at 11:46
  • 4
    $\begingroup$ Also consider that "in random order" is really a red herring up to relabeling. That should make computer experiments a lot easier... $\endgroup$
    – chubakueno
    Jun 15, 2014 at 16:00
  • 12
    $\begingroup$ @chubakueno We need a total of ${n\choose 2}$ pairs of people to sit next to each other. With regard to $f$, each time we perform a switch we add at most $2$ pairs. With regard to $g$, each time we perform a switch we add at most $4$ pairs. Since we already have $n$ pairs from the initial arrangement we have $2f(n)\ge{n\choose2}-n$ and $4g(n)\ge{n\choose2}-n$, which reduces to $f(n)\ge\frac{1}{4}n(n-3)$ and $g(n)\ge\frac{1}{8}n(n-3)$. $\endgroup$ Jul 1, 2014 at 17:38
  • 6
    $\begingroup$ @chubakueno, one upper bound for $f(n)$ is $\frac{1}{2}(n^2 - 3n + 2)$. Imagine $1...n$ in a line; $(1--n)$ is the circle connection. Move 1 all the way to between $n-1$ and $n$. That's $n-2$ moves, and $1$ has all its neighbors, plus $(2--n)$ from the circle connection. Bubble $2$ up until it is between $n-1$ and $1$ -- $n - 3$ moves. $2$ has all connections and $(3--n)$ is the circle connection. Keep going until you hit $(n-2)(n-1)(n-3)(n-4)...(2)(1)(n)$. You should get $(n-2) + (n-3) + \dotsb + 1$. $\endgroup$ Jul 3, 2014 at 22:34

2 Answers 2

6
$\begingroup$

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)]
$\endgroup$
17
  • $\begingroup$ Thanks for writing this up! Could you elaborate on your representation for the graphs (once you've cleaned up the code) - I think that'll really add to this answer. Also, when you say that an exhaustive search is no longer feasible for $n>13$, you do mean that it's possible but will just take much more time, right? $\endgroup$ Jan 21, 2017 at 21:33
  • $\begingroup$ Post updated with a brief explanation of my canonicalization function. For n=13 there are 50,502,031,367,952 non-isomorphic graphs. By empirical results I'm guessing the state-space is ~1/5 that. So... yea even 13 is probably not tractable. $\endgroup$ Jan 21, 2017 at 22:48
  • $\begingroup$ Thank you for the list of solutions -- it matches what my exhaustive search coded in C found (so either we both have the same mistake in our codes, or both work well ;-) ). My search was not using any special heuristics apart from the one which compared number of missing edges in the graph with the total number of steps remaining until the best known solution (since each steps adds at most four edges); did you employ something such to reduce the number of explored states? $\endgroup$ Jan 22, 2017 at 10:47
  • $\begingroup$ Also, it would be nice to have the best results found for $n=10$ and $n=11$ confirmed by independent exhaustive search; although I trust my program, mistakes can always happen :-) Of course, $n=12$ and $n=13$ aren't necessary, since they already match the proven lower bound and beyond that the (exhaustive) search really looks intractable so far. $\endgroup$ Jan 22, 2017 at 10:49
  • 1
    $\begingroup$ @VincentTjeng Meanhwile, a DFS with two additional restrictions (one person doesn't move, plus each swap needs to be worse or equal to the previous one in terms of newly added edges to the friendship graph) has found a solution confirming $g(14)=20$ (I'll add it in a comment to the question). Of course, as we know from $n=8$, this approach is not guaranteed to find the optimal solution in all cases. $\endgroup$ Jan 26, 2017 at 9:49
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .