Simple Combinatorial Gray Codes Constructed by Reversing Sublists
Simple Combinatorial Gray Codes Constructed by Reversing Sublists
复制标题
由反转子表构造的简单组合格雷码
DOI：
10.1007/3-540-57568-5_250
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
F. Ruskey
中科院分区：
文献类型：
--
作者：
F. Ruskey
我们提出了三个相关的结果，简单的组合格雷码构造递归反转某些子列表。首先，我们显示了一个双射之间的列表组成的克努特和列表的组合Eades和麦凯。其次，我们提供了一个简短的描述的一个列表的组合满足更严格的接近标准的大通。最后，我们开发了一个新的，简单的描述，格雷码列表的分区的一组成一个固定数量的块，所表示的限制增长序列。在每种情况下，列表的递归定义都可以很容易地转换成用于在与列表中的元素数量成比例的时间上生成列表的算法;即，每个对象的生成时间为O（1）摊销时间。
We present three related results about simple combinatorial Gray codes constructed recursively by reversing certain sublists. First, we show a bijection between the list of compositions of Knuth and the list of combinations of Eades and McKay. Secondly, we provide a short description of a list of combinations satisfying a more restrictive closeness criteria of Chase. Finally, we develop a new, simply described, Gray code list of the partitions of a set into a fixed number of blocks, as represented by restricted growth sequences. In each case the recursive definition of the list is easily translatable into an algorithm for generating the list in time proportional to the number of elements in the list; i.e., each object is produced inO(1) amortized time by the algorithm.