I found this question from Anurag Bishnoi’s post on circular sorting. The problem was introduced by Adin, Alon, and Roichman in Circular sorting.

Put the numbers $1,2,\ldots,n$ around a circle in some order. You can swap any two numbers. How many swaps might you need before the numbers appear in clockwise order? It is relevant that the numbers are in a circle. A sorted circle can begin with the $1$ anywhere.

Here’s some notation Adin, Alon, and Roichman use. The number $t([\pi])$ is the minimum number of swaps needed to sort one particular circular arrangement $\pi$. The number $t(n)$, called the circular sorting number, is the largest such minimum among all arrangements of $n$ labels:

\[t(n)=\max_{\pi\in S_n}t([\pi]).\]

They showed that for any prime $p$, $t(p)=p-2$ and conjectured that the circular sorting number is less than $n-2$ for all composite $n$. Bastide, Bishnoi, Groenland, Gijswijt and Joshi proved that $t(n)\le n-3$ when $n\ge4$ is divisible by 2 or 3. With this upper bound, combined with a computational search, they were able to compute $t(n)$ for many small composite $n$. The smallest value of $n$ for which they could not determine $t(n)$ was $n=22$. The upper bound gives $t(22) \leq 22-3 = 19$ and they found that the circular sorting number was at least 18, but it could still be either $18$ or $19$.

I ran a search that found an arrangement requiring exactly 19 swaps, which means we now know that

\[t(22)=19.\]

Here’s an explanation of my code.

Counting cycles

First fix a target order, so that label $i$ belongs at position $i$. An arrangement is then a permutation $\pi$: the entry $\pi(i)$ tells us which label is currently at position $i$.

For example, consider the six-entry list

0, 2, 3, 1, 5, 4

Its disjoint cycles are $(0)(1\,2\,3)(4\,5)$. The fixed point needs no swaps, the 3-cycle needs two, and the 2-cycle needs one. Sorting to the fixed target therefore takes three swaps.

In general, a cycle of length $\ell$ takes $\ell-1$ swaps to sort. If the permutation has $C$ cycles, including fixed points, this gives $n-C$ swaps. Fewer are impossible: each transposition can increase the number of cycles by at most one, and the identity has $n$ cycles. Thus

\[t(\pi)=n-\operatorname{cyc}(\pi).\]

On a circle, we can choose any starting position. Write $c(x)=x+1\pmod n$, and compose maps from right to left. The shifted permutation $\pi c^k$ sends $x$ to $\pi(x+k)$, with indices taken modulo $n$. Trying all starting positions gives

\[t([\pi]) =\min_{0\le k<n}\bigl(n-\operatorname{cyc}(\pi c^k)\bigr) =n-\max_{0\le k<n}\operatorname{cyc}(\pi c^k).\]

More cycles mean easier sorting. To find a difficult circular arrangement, we must prevent every shift from having too many cycles.

Giving the search something to improve

For $n=22$, the goal is to find a permutation whose 22 shifts all have at most three cycles. If even one shift has four cycles, it gives a way to sort the circle in $22-4=18$ swaps.

You might try to minimize the largest cycle count directly, but consider two candidates with at most four cycles in any shift where one has four cycles in just one shift and the other has four cycles in several shifts. The maximum gives them the same score, even though the second violates our target in more places.

So instead, I used the penalty

\[F(\pi)=\sum_{k=0}^{21} \max\bigl(\operatorname{cyc}(\pi c^k)-3,0\bigr)^2.\]

Each shift contributes as follows:

Cycles in a shift Contribution to $F$
3 or fewer 0
4 1
5 4
6 9

The score counts excess cycles, and larger excesses are penalized more heavily. Fewer or less severe violations reduce the penalty. Then when every rotation gets to just three cycles, the score is zero.

Keeping track of a candidate

We store the permutation in p. For each shift k, cc[k] stores its cycle count, and id[k][x] identifies the cycle containing x. Only equality of these identifiers matters.

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

using namespace std;

struct State {
    int n;
    vector<int> p, cc;
    vector<vector<int>> id;
    double score;

    State(int n) : n(n), p(n), cc(n), id(n, vector<int>(n)) {
        iota(p.begin(), p.end(), 0);
    }
}

To fill those arrays, follow each unvisited point until its cycle closes. For shift k, the next point after y is p[(y + k) % n].

void rebuild() {
    score = 0;

    for (int k = 0; k < n; k++) {
        fill(id[k].begin(), id[k].end(), -1);
        int c = 0;

        for (int x = 0; x < n; x++)
            if (id[k][x] < 0) {
                int y = x;
                do {
                    id[k][y] = c;
                    y = p[(y + k) % n];
                } while (y != x);
                ++c;
            }

        cc[k] = c;
        score += cost(c);
    }
}

static double cost(int c) {
    return c <= 3 ? 0 : (c - 3) * (c - 3);
}

One cycle decomposition visits $n$ points. Doing this for all $n$ shifts takes $O(n^2)$ time, and the membership array occupies $O(n^2)$ space.

Making proposed swaps cheap

Suppose we exchange the entries of p at positions $a$ and $b$. This changes $\pi$ to $\pi\tau$, where $\tau=(a\,b)$. For shift $k$,

\[(\pi\tau)c^k =(\pi c^k)(c^{-k}\tau c^k).\]

So the corresponding change to $\pi c^k$ is a transposition of the points $a-k$ and $b-k$, modulo $n$.

There’s only two possibilities:

  • If those points lie in the same cycle, the transposition splits it into two, increasing the cycle count by one.
  • If they lie in different cycles, it merges them, decreasing the count by one.

The cached memberships tell us which case applies so we can predict the new count and its contribution to $F$ without traversing any cycles.

double delta(int a, int b) {
    double d = 0;

    for (int k = 0; k < n; k++) {
        int x = (a - k + n) % n, y = (b - k + n) % n;
        int nc = cc[k] + (id[k][x] == id[k][y] ? 1 : -1);
        d += cost(nc) - cost(cc[k]);
    }

    return d;
}

This evaluates a proposed swap in $O(n)$ time because it just does one constant-time check for each shift. If we accept the swap, we rebuild all the memberships in $O(n^2)$. If we reject it, we don’t need to do anything, which is good because, in the successful run, about 98% of proposals were rejected.

Choosing starting points

Here is the beginning of main. Its arguments specify the number of labels, time budget, random seed and output filename. It also tracks the best candidate and the numbers of proposed and accepted moves.

int main(int argc, char** argv) {
    int n = argc > 1 ? atoi(argv[1]) : 22;
    double seconds = argc > 2 ? atof(argv[2]) : 60;
    uint64_t seed = argc > 3 ? strtoull(argv[3], 0, 10) : 20261020;
    string file = argc > 4 ? argv[4] : "work/search_result.json";

    mt19937_64 rng(seed);
    State s(n), best(n);
    double bestscore = 1e99;
    uint64_t moves = 0, accepts = 0, restarts = 0;

    auto start = chrono::steady_clock::now();
    auto elapsed = [&]() {
        return chrono::duration<double>(chrono::steady_clock::now() - start).count();
    };

    vector<vector<int>> seeds;
}

For nonzero $a,b$ modulo the prime $q=23$, consider maps that multiply a nonzero square by $a$ and a nonsquare by $b$, sending zero to zero. Taking $a=b$ includes affine examples with zero translation. We retain maps that are permutations and whose largest shifted cycle count is two. From each retained map, we delete one entry and compress the remaining labels to $0,\ldots,21$.

int q = n + 1;
bool prime = true;
for (int d = 2; d * d <= q; d++)
    if (q % d == 0)
        prime = false;

if (prime) {
    vector<int> sq(q);
    for (int x = 1; x < q; x++)
        sq[x * x % q] = 1;

    for (int a = 1; a < q; a++)
        for (int b = 1; b < q; b++) {
            vector<int> f(q);
            for (int x = 0; x < q; x++)
                f[x] = (sq[x] ? a : b) * x % q;

            vector<int> seen(q);
            bool perm = true;
            for (int v : f)
                if (seen[v]++)
                    perm = false;
            if (!perm)
                continue;

            State t(q);
            t.p = f;
            t.rebuild();
            if (*max_element(t.cc.begin(), t.cc.end()) != 2)
                continue;

            for (int j = 0; j < q; j++) {
                vector<int> v;
                int label = f[j];
                for (int i = 0; i < q; i++)
                    if (i != j)
                        v.push_back(f[i] - (f[i] > label));
                seeds.push_back(v);
            }
        }
}

for (auto& p : seeds) {
    s.p = p;
    s.rebuild();
    if (s.score < bestscore) {
        best = s;
        bestscore = s.score;
    }
}

We save the best permutation, its cycle counts and the run statistics as JSON.

auto save = [&]() {
    ofstream out(file);
    out << "{\"n\":" << n
        << ",\"seed\":" << seed
        << ",\"score\":" << bestscore
        << ",\"moves\":" << moves
        << ",\"accepts\":" << accepts
        << ",\"restarts\":" << restarts
        << ",\"seconds\":" << elapsed()
        << ",\"permutation\":[";
    for (int i = 0; i < n; i++)
        out << (i ? "," : "") << best.p[i];
    out << "],\"cycle_counts\":[";
    for (int i = 0; i < n; i++)
        out << (i ? "," : "") << best.cc[i];
    out << "]}\n";
};

if (!seeds.empty()) {
    cerr << "seeds=" << seeds.size() << " initial score=" << bestscore << "\n";
    save();
}

Local minima

A greedy search that only accepts improvements can get trapped. Sometimes every nearby swap may look worse but you have to go one of them to get to a better arrangement.

The search uses simulated annealing. Let $\Delta$ be the proposed change in $F$. Moves with $\Delta\le0$ are always accepted. A worse move is accepted with probability

\[e^{-\Delta/T},\]

where $T$ is a temperature. Higher temperatures allow more exploration. As the temperature falls, the search becomes less willing to accept increases in the penalty.

Each restart allows up to 20,000 proposals, cooling geometrically from a temperature chosen between 1 and 3.99 toward 0.08. When a restart ends, we choose another starting point. The program stops when it finds score zero or reaches its time budget.

while (elapsed() < seconds && bestscore > 0) {
    ++restarts;

    if (!seeds.empty() && rng() % 3 == 0)
        s.p = seeds[rng() % seeds.size()];
    else if (bestscore < 1e90 && rng() % 3 == 0) {
        s.p = best.p;
        for (int j = 0; j < int(rng() % 8); j++)
            swap(s.p[rng() % n], s.p[rng() % n]);
    } else {
        iota(s.p.begin(), s.p.end(), 0);
        shuffle(s.p.begin(), s.p.end(), rng);
    }
    s.rebuild();

    int steps = 20000;
    double hi = 1.0 + double(rng() % 300) / 100.0, lo = .08;

    for (int j = 0; j < steps && bestscore > 0; j++) {
        ++moves;
        int a = rng() % n, b = rng() % (n - 1);
        if (b >= a)
            ++b;

        double d = s.delta(a, b), temp = hi * pow(lo / hi, double(j) / steps);
        if (d <= 0 || generate_canonical<double, 53>(rng) < exp(-d / temp)) {
            swap(s.p[a], s.p[b]);
            s.rebuild();
            ++accepts;

            if (s.score < bestscore) {
                bestscore = s.score;
                best = s;
                cerr << "seconds=" << elapsed() << " moves=" << moves
                        << " best=" << bestscore
                        << " maxcycles=" << *max_element(best.cc.begin(), best.cc.end())
                        << "\n";
                save();
            }
        }

        if (moves % 20000 == 0 && elapsed() >= seconds)
            break;
    }
}

save();
cout << "n=" << n << " moves=" << moves << " score=" << bestscore
        << " maxcycles=" << *max_element(best.cc.begin(), best.cc.end())
        << " seconds=" << elapsed() << "\n";

Running the program

Here’s the exact arguments I used when running the program:

c++ -O3 -std=c++17 search-t22.cpp -o search-t22
./search-t22 22 600 20261020 result22.json

The arguments request 22 labels, a budget of roughly ten minutes, random seed 20261020, and the output file result22.json.

The saved successful run recorded:

Quantity Value
Random seed 20261020
Proposed swaps 881,130,216
Accepted swaps 18,478,142
Restarts started 44,057
Final penalty 0
Recorded elapsed time 75.1718 seconds

The witness found in that run was

16, 2, 20, 5, 1, 6, 14, 12, 19, 4, 7,
10, 15, 0, 18, 3, 21, 17, 13, 9, 11, 8

After the search, I normalized it using symmetries that preserve the sorting distance: cyclic changes of the position and label origins, and simultaneous multiplication of the coordinates by an invertible residue. This produced the arrangement below. More explicitly, if $p$ is the raw permutation, the displayed one is

\[\pi(i)=17p(13i+16)+17\pmod{22}.\]

The multipliers 13 and 17 are inverses modulo 22. These transformations preserve the multiset of shifted cycle counts, although they can change their order.

The result

The resulting clockwise arrangement is

0, 1, 6, 11, 5, 2, 13, 16, 4, 7, 15,
9, 18, 19, 3, 17, 12, 20, 10, 21, 8, 14

Direct decomposition of its 22 shifts gives

\[\operatorname{cyc}(\pi c^k)= \begin{cases} 3,&k\text{ even},\\ 2,&k\text{ odd}. \end{cases}\]

For example, the unshifted permutation has the cycles

\[(0)(1)(2\,6\,13\,19\,21\,14\,3\,11\,9\,7\,16\,12\,18\,10\,15\,17\,20\,8\,4\,5).\]

Its two fixed points and one 20-cycle give a sorting procedure using 19 swaps. Checking all the other shifts proves that no choice of starting point allows fewer. Therefore

\[t([\pi])=22-\max_k\operatorname{cyc}(\pi c^k)=22-3=19.\]

This witness establishes $t(22)\ge19$. The existing upper bound supplies $t(22)\le19$, so

\[\boxed{t(22)=19.}\]