xi. Operations and Reachable States

“Can array $a$ be turned into $b$ by these operations?” The answer is almost always: compute a canonical form (or a full set of invariants) for both and compare. To prove it you need both directions: the invariants are preserved (necessity) and any two states with equal invariants are connected (sufficiency, usually by a normalisation procedure).

Operation	Reachable iff
swap $a_i$, $a_{i+k}$	each residue class $i\mathrm{mod}k$ has the same multiset
swap adjacent elements	same multiset
swap adjacent elements with $a_i+a_{i+1}$ odd (or any property of pairs)	elements that can never pass each other keep their relative order
reverse any substring of length $k$ (odd $k$)	depends on $k$: positions keep parity classes
cyclic shift of the whole array	$b$ is a substring of $a+a$
$a_i+=a_{i-1}$ style prefix operations	look at difference or prefix arrays instead
operations commute	only the count of each operation matters

bool reachableByKSwaps(vector<int> a, vector<int> b, int k) {
    int n = sz(a);
    for (int r = 0; r < k; r++) {
        vector<int> x, y;
        for (int i = r; i < n; i += k) x.push_back(a[i]), y.push_back(b[i]);
        sort(all(x)), sort(all(y));
        if (x != y) return false;
    }
    return true;
}

Proof: swaps at distance k

A swap of $a_i$ and $a_{i+k}$ exchanges two elements of the same residue class, so each class’s multiset is invariant. Conversely, within one class the positions $r,r+k,r+2k,\dots$ form a path where consecutive positions can be swapped, and adjacent transpositions generate every permutation of a path, so any arrangement of each class is reachable independently. Verified by BFS on random arrays of length $\le 6$.

Normal forms

• Operations that commute and are self-inverse (xor with a fixed mask, flipping a row or a column): each is used 0 or 1 times, so the state space is a vector space over GF(2). Reachability is a linear system; see XOR Basis.
• Operations that move “tokens” between neighbours: track the prefix sums; each operation changes one prefix sum by $\pm 1$.
• If an operation can be undone, reachability is an equivalence relation; pick the lexicographically smallest member as the canonical form and compute it greedily.

Related: Constructive Algorithms, Parity and Coloring.