The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization

Abstract

A new data structure "Q-sequence" for representing a floorplan of n rooms is proposed. The Q-sequence is a concatenation of room names and two kinds of positional symbols, totally of length 3n. It is shown that encoding of a given floorplan and decoding to a floorplan are both possible in a linear time of n. An exact counting formula of distinct floorplans is given. Numerical estimation shows that the number is only slightly larger than that of a slicing structure, and far smaller than (n!)/sup 2/ which is the size of the packing solution space by the sequence-pair representation.