文章基本信息

标题：GRAY CODE AND HAMMING DISTANCE FOR GRAPH OF Sn(123,132)
本地全文：下载
作者：A. JUARNA ; A.B. MUTIARA
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2011
卷号：32
期号：1
页码：15-19
出版社：Journal of Theoretical and Applied
摘要：As we noted that an isomorphism between two combinatorial classes is a closeness preserving bijection between those classes, that is, two objects in a class are closed if and only if their images by this bijection are also closed. Often, as in this paper, closeness is expressed in terms of Hamming distance. Isomorphism allows us to find out some properties of a combinatorial class X (or for the graph induced by the class X) if those properties are found in the pre image of the combinatorial class X; some mentioned properties are hamiltonian path, graph diameter, exhaustive and random generation, and ranking and unranking algorithms. Simion and Schmidt showed in 1985 that the cardinality of the set Sn(123,132) length n permutations avoiding the patterns 123 and 132, is 2n-1, but in the other side 2n-1 is the cardinality of the set Bn-1 = {0,1}n-1 of length (n-1) binary strings. Theoretically, it must exist a bijection between Sn(123,132) and Bn-1. In this paper we give a constructive bijection between Bn-1 and Sn(123,132); we show that it is actually an isomorphism and illustrate this by constructing a Gray code for Sn(123,132) from a known similar result for Bn-1.
关键词：Pattern-Avoiding Permutations; Binary Strings; Constructive Bijection; Hamming Distance; Combinatorial Isomorphism