The Bell Ringers Who Ran an Algorithm Since 1668

A tower full of ringers pulling on ropes is, whether anyone in the belfry admits it, running a combinatorial generation algorithm. The rules force it. A hanging bell is a pendulum with its own fixed swing, so a ringer can nudge its strike a little earlier or a little later but cannot yank it from fourth place to first. Between one row and the next, a bell can only trade places with a neighbour. And a proper extent must ring every arrangement of the bells exactly once before returning home.

Read those two constraints back to back and you have a precise specification: enumerate all n! permutations such that consecutive ones differ by a single adjacent transposition. Fabian Stedman wrote this down as “plain changes” in 1668. Three centuries later Steinhaus, Johnson, and Trotter published the same procedure as an algorithm, and it turns up in Knuth under exactly that name.

The trick is to give every bell a direction. On each row you find the largest bell that is “looking” at a smaller neighbour, swap it that way, then reverse the direction of everyone bigger than it. Repeat until nobody can move.

def plain_changes(n):
    perm = list(range(1, n + 1))
    dirs = [-1] * n
    yield perm[:]
    while True:
        mob = -1
        for i in range(n):
            j = i + dirs[i]
            if 0 <= j < n and perm[i] > perm[j] and (mob < 0 or perm[i] > perm[mob]):
                mob = i
        if mob < 0:
            return
        j = mob + dirs[mob]
        perm[mob], perm[j] = perm[j], perm[mob]
        dirs[mob], dirs[j] = dirs[j], dirs[mob]
        for i in range(n):
            if perm[i] > perm[j]:
                dirs[i] = -dirs[i]
        yield perm[:]

On four bells that walks through all 24 rows, opening 1234, 1243, 1423, 4123… and closing on 2134, one step from the start. The same logic in Zig, arrays fixed on the stack, no allocator in sight:

fn plainChanges(n: usize, comptime emit: fn ([]const u8) void) void {
    var perm: [16]u8 = undefined;
    var dir: [16]i8 = undefined;
    for (0..n) |i| { perm[i] = @intCast(i + 1); dir[i] = -1; }
    emit(perm[0..n]);
    while (true) {
        var mob: ?usize = null;
        for (0..n) |i| {
            const j = @as(i64, @intCast(i)) + dir[i];
            if (j < 0 or j >= n) continue;
            const k: usize = @intCast(j);
            if (perm[i] > perm[k] and (mob == null or perm[i] > perm[mob.?])) mob = i;
        }
        const m = mob orelse return;
        const j: usize = @intCast(@as(i64, @intCast(m)) + dir[m]);
        std.mem.swap(u8, &perm[m], &perm[j]);
        std.mem.swap(i8, &dir[m], &dir[j]);
        for (0..n) |i| if (perm[i] > perm[j]) { dir[i] = -dir[i]; };
        emit(perm[0..n]);
    }
}

Both print byte-for-byte identical extents. The adjacency rule that the belfry treats as a physical inconvenience is the whole reason this generates a Gray code over permutations: no bell ever teleports, so no arrangement is skipped and none repeats. On eight bells the full extent is 40,320 rows and takes about eighteen hours to ring — the same loop above, run by tired humans instead of a while statement, which is roughly the part I keep thinking about.