Sorting A = 0k1n−k
to A* = 1n−k0k
via generators of the CC3 Schreier graph
Parameters
3 ≤ n ≤ 14
1 ≤ k ≤ n−1
Generators
Start to see moves
Transformation
Current Move
Press START to compute the shortest path and begin.
Consecutive 3-Cycle Moves
The Problem
Starting from the binary string A with k zeros followed by
n−k ones, find the shortest sequence of consecutive 3-cycle generators
that reaches the fully sorted string A* (ones first):
A = 0k 1n−k = 00…0 11…1
A* = 1n−k 0k = 11…1 00…0
The path is computed by breadth-first search (BFS) over the CC3 Schreier
coset graph, guaranteeing minimum length.
Generators
A consecutive 3-cycle σi acts on positions i, i+1,
i+2 only. Two orientations serve as generators:
σi (right-rotate): (a, b, c) ↦ (c, a, b)
σi⁻¹ (left-rotate): (a, b, c) ↦ (b, c, a)
Applying σi three times returns to the original string.
The generators for i = 0, 1, …, n−3 connect all C(n, k) binary strings
of the same weight into a single graph.
Decomposition & Arrow Colors
Every 3-cycle decomposes into two adjacent transpositions.
On a binary string, a transposition τj,j+1 is effective
only when bits j and j+1 differ. The number of effective swaps
determines the arrow and generator color:
Red — both transpositions effective (e.g. (0,0,1)→(1,0,0))
1
Blue — only one transposition effective (e.g. (0,1,0)→(0,0,1))
Reading the Display
The curved arrows below the cells preview the next move —
each arrow shows where one bit will travel. Arrowheads sit at the midpoint
of each curve. The orange cells mark the triple operated on
by the most recent generator. The Generators column on the
left logs every applied move with its color and position triple.
Cell Legend
0
Bit value 0
1
Bit value 1
●
Active triple
Controls
Start — run BFS and show the initial state.
Next Step — apply the next generator; curved arrows preview the one after.
Back — undo the last generator.
Reset — return to A and clear the log.
n / k — adjust string length and zero count; resets automatically.
Keyboard: → or Space = Next Step · ← = Back · Esc = close Help