Twin Binary Sequences

The idea

Mosaic floorplans have a hidden binary-tree skeleton: slice off blocks from one corner and the branching pattern of the demolition forms a tree. Twin Binary Sequences capture a mosaic floorplan as a block permutation plus two bit sequences derived from twin binary trees, a classical combinatorial pairing in which two labeled trees are twins when their in-order traversals agree and their bit labelings are complementary. The twin condition is exactly what makes the encoding tight: every valid tuple corresponds to one and only one mosaic floorplan, and every mosaic floorplan to one tuple.

Non-redundancy is the headline. The sequence pair wanders an (n!)² space; corner block lists admit multiple encodings of the same floorplan; twin binary sequences are a bijection, so the annealer never wastes a move revisiting the same floorplan under a different name. The authors also gave a linear-time decode and showed how to insert empty rooms where beneficial without the guesswork dummy blocks of the corner block list, closing the gap between mosaic and general packings.

Trade-offs

The bookkeeping is more delicate than a tree you can freely rotate: moves must preserve the twin property, and the combinatorial correspondence takes longer to internalize than "left child means to my right". In exchange you search the smallest possible space for mosaic topologies.

Where you meet it today

In the theory of floorplan enumeration (twin binary trees are how mosaic floorplans were tied to Baxter numbers) and in floorplanners that prize non-redundant search spaces. It marks the endpoint of the mosaic-encoding line that corner block lists began.