Enumerating Floorplans with n Rooms
Enumerating Floorplans with n Rooms
复制标题
枚举包含 n 个房间的平面图
DOI：
10.1007/3-540-45678-3_10
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Shin
中科院分区：
文献类型：
--
作者：
Shin
如果每个面（包括外面）都是矩形，则称为平面图的平面绘图。基础平面布置图是在外表面有指定基线段的平面布置图。在本文中，我们给出了一个简单的算法，以生成所有基于平面图与大多数面。该算法使用o (n)空间并生成。每层平面图1次，不得重复。该算法不输出整个平面图，而是输出与之前平面图的差异。通过修改算法，我们可以不重复地生成所有基于平面图的平面图，每个平面图具有精确的面数inO(1)。此外，我们可以在没有重复的情况下生成所有（非基于）平面图，每个平面图都具有精确的面。
A plane drawing of a graphis called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at mostnfaces. The algorithm usesO(n)space and generates such. oorplans inO(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactlynfaces inO(1) time per floorplan. Also we can generate without duplications all (non-based) floorplans having exactlynfaces inO(n) time per floorplan.