Skip to content

Adjacent-Swap Sequence

Method — instantiates Mobile-Defect Reconfiguration

Reorders a coupled sequence toward its target by a chain of legal neighbor exchanges — each swap moves one mismatch a single step without disturbing the rest.

Adjacent-Swap Sequence is the archetype's elementary reordering move. It treats a single out-of-place neighbor relation as the mobile defect and walks it toward its target position by exchanging adjacent elements, one legal swap at a time, so the substrate is only ever locally disturbed. Its defining trait is that it is discrete and order-preserving: every swap touches exactly one relation and leaves the entire rest of the sequence intact, so the structure is never globally disassembled. Where a continuous glide slides a defect along a corridor, this mechanism advances it in named, individually-legal transpositions — which makes each step auditable and, if needed, reversible.

Example

A yard crew must resequence a cut of tank cars so a single propane car ends up next to the road engine for a spur delivery. There is one short lead and no room to pull the cut apart, so the whole train can't be re-laid at once. The switcher instead bubbles the propane car to its slot: swap it with its neighbor, then the next, then the next, advancing it one coupling at a time. Each exchange is allowed only if the two cars may legally sit adjacent — a placarding rule forbids the propane car beside a car of oxidizer, so that swap is skipped and routed around. Every intermediate arrangement stays a legal, coupled, movable train, and only one car's position changes per step. The cut reaches its target order without ever ceasing to be a train.

How it works

  • Frame each out-of-order pair as an inversion — a local mismatch to be undone.
  • Move by transposition — each swap exchanges two neighbors and removes exactly one inversion, cutting the distance to target by one.
  • Gate every swap on local legality — the pair may exchange only if the move keeps the neighborhood valid; forbidden adjacencies are routed around.
  • Preserve everything else — because only the swapped adjacency changes, all other relations, and the global topology of the sequence, carry through untouched.

Tuning parameters

  • Swap granularity — single element versus a block moved as a unit. Coarser blocks reach the target in fewer moves but enlarge each local disturbance.
  • Legality strictness — how tight the per-swap admissibility rule is. Stricter rules forbid more intermediate states (safer) but can dead-end a route.
  • Route and direction — which way to bubble a defect and around which forbidden pairs. Changes the swap count and which regions are perturbed.
  • Interleaving — whether several defects are bubbled in one pass or strictly one at a time. Interleaving is faster but risks two fronts colliding.

When it helps, and when it misleads

Its strength is that it is the right move when only local rearrangement is available and a global re-lay is impossible, unsafe, or would break continuity — it converts an intractable simultaneous reshuffle into a chain of small, legal, individually-reversible steps.

Its cost, though, is quadratic in disorder: a sequence with many inversions needs many swaps, and crawling a far-displaced element across the whole structure can be dramatically more expensive than a single global sort.[1] The classic misuse is reaching for adjacent swaps out of habit on a substrate that could be re-laid globally more cheaply — paying O(n²) local churn to avoid a one-time cutover that was actually the better trade. The discipline is to size the disorder first (count the inversions, or the displacement of the worst element) and choose gliding only when local-only really is the binding constraint.

How it implements the components

  • mobile_defect_definition — fixes the unit defect as a single out-of-place adjacency, the thing that gets moved.
  • local_move_legality_rule — each swap fires only when the neighboring pair is legally exchangeable; illegal adjacencies are routed around.
  • topology_preservation_check — by construction every swap alters exactly one relation, so the sequence's global structure is preserved step to step.

It does not supply the motive machinery or the route itself — mobility_enabler and propagation_corridor_map belong to Localized Defect Glide Method — nor the target ordering and orchestration, which come from Rolling State-Migration Workflow.

Notes

Adjacent-Swap Sequence is the discrete cousin of continuous defect glide: it applies when moves are restricted to nearest-neighbor exchanges. When non-adjacent or long-range moves are legal, the reordering is a different — and often cheaper — mechanism, not this one.

References

[1] In permutation terms, the minimum number of adjacent transpositions that sorts a sequence equals its number of inversions (out-of-order pairs) — the basis of bubble and insertion sort. That count is the honest price tag of local-only reordering, and comparing it against a global re-sort is the check that keeps the method from being used where it does not pay. ↩