检索结果-内蒙古大学图书馆

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Qiu, Yuan Williams, Aaron Williams Coll Williamstown MA 01267 USA

ISBN: (纸本)9783031555978;9783031555985

We provide a simple approach to generating all 2(n) center dot n! signed permutations of [n] = {1, 2,..., n}. Our solution generalizes the most famous ordering of permutations: plain changes (Steinhaus-Johnson-Trotter algorithm). In plain changes, the n! permutations of [n] are ordered so that successive permutations differ by swapping a pair of adjacent symbols, and the order is often visualized as a weaving pattern on n ropes. Here we model a signed permutation as n ribbons with two distinct sides, and each successive configuration is created by twisting (i.e., swapping and turning over) two neighboring ribbons or a single ribbon. By greedily prioritizing 2-twists of large symbols then 1-twists of large symbols, we create a signed version of plain change's memorable zig-zag pattern. We also provide a loopless implementation (i.e., worst-case O(1)-time per object) by enhancing the well-known mixed-radix Gray code algorithm.

关键词： plain changes signed permutations signed permutohedron greedy Gray codes combinatorial generation loopless algorithms

来源：评论

学校读者我要写书评

暂无评论

An Improved Algorithm for Ranking Zaks' Sequences in Gray-code Order

An Improved Algorithm for Ranking Zaks' Sequences in Gray-co...

引用

2015 International Conference on Computer Science and Information Systems (ICCSIS-15);International Conference on Mechatronics and Production Processes (ICMPP’2015);2015 International Conference on Environment and Civil Engineering (ICEACE’2015)

作者： Ro-Yu Wu Chir-Ho Chang Jou-Ming Chang Department of Industrial Management Lunghwa University of Science and Technology

A k-ary tree is a rooted and ordered tree such that every internal node has exactly k children. A natural representation of k-ary trees is the use of z-sequences introduced by Zaks in 1980. Under such representations, algorithms for generating z-sequences of k-ary trees in Gray-code order was independently developed by van Baronaigien(2000) and Xiang et al.(2000). Based on such a Gray-code order, Ahmadi-Adl et al.(2011) recently proposed ranking and unranking algorithms and showed that each algorithm can be run in O(kn2) time, where n is the number of internal nodes in a k-ary tree. In this paper, we make an improvement of the ranking algorithm. The time complexity and space requirement in our algorithm are O(max{n2,kn}) and O(kn), respectively.

关键词： loopless algorithms ranking algorithms lexicographic order Gray-code order

来源：评论

学校读者我要写书评

暂无评论

Ranking and Unranking of Non-regular Trees in Gray-Code Order

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2013年第6期E96A卷 1059-1065页

作者： Wu, Ro-Yu Chang, Jou-Ming Chen, An-Hang Ko, Ming-Tat Lunghwa Univ Sci & Technol Dept Ind Management Tao Yuan Taiwan Natl Taipei Coll Business Inst Informat & Decis Sci Taipei Taiwan Acad Sinica Inst Informat Sci Taipei Taiwan

A non-regular tree T with a prescribed branching sequence (s(1), s(2), ... , s(n)) is a rooted and ordered tree such that its internal nodes are numbered from I to a in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n(2)) time and O(n(2) + nS(n-1)) time, respectively, provided a preprocessing takes O(n(2)S(n-1)) time and space in advance, where Sn-1 = Sigma(n-1)(i=1)(s(i) - 1).

关键词： loopless algorithms ranking algorithm unranking algorithm lexicographic order Gray-code order non-regular trees

来源：评论

学校读者我要写书评

暂无评论

Cool-lex order and k-ary Catalan structures

引用

JOURNAL OF DISCRETE algorithms 2012年 16卷 287-307页

作者： Durocher, Stephane Li, Pak Ching Mondal, Debajyoti Ruskey, Frank Williams, Aaron Univ Manitoba Dept Comp Sci Winnipeg MB Canada Univ Victoria Dept Comp Sci Victoria BC Canada McGill Univ Dept Math & Stat Montreal PQ Canada

For any given k, the sequence of k-ary Catalan numbers, C-t,C-k = (Sic), enumerates a number of combinatorial objects, including k-ary Dyck words of length n = kt and k-ary trees with t internal nodes. We show that these objects can be efficiently ordered using the same variation of lexicographic order known as cool-lex order. In particular, we provide loopless algorithms that generate each successive object in O(1) time. The algorithms are also efficient in terms of memory, with the k-ary Dyck word algorithm using O(1) additional index variables, and the k-ary tree algorithm using O(t) additional pointers and index variables. We also show how to efficiently rank and unrank k-ary Dyck words in cool- lex order using O(kt) arithmetic operations, subject to an initial precomputation. Our results are based on the cool-lex successor rule for sets of binary strings that are bubble languages. However, we must complement and reverse 1/k-ary Dyck words to obtain the stated efficiency. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Catalan structures Cool-lex order Bubble langauges loopless algorithms Ranking k-ary Dyck words k-ary trees

来源：评论

学校读者我要写书评

暂无评论

Fusing loopless algorithms for combinatorial generation

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2007年第2期18卷 263-293页

作者： Takaoka, Tadao Violich, Stephen Univ Canterbury Dept Comp Sci & Software Engn Christchurch 1 New Zealand

Some combinatorial generation problems can be broken into subproblems for which loopless algorithms already exist. This article discusses means by which loopless algorithms can be fused to produce a new loopless algorithm that solves the original problem. It demonstrates this method with two new loopless algorithms. The first generates well-formed parenthesis strings containing two different types of parentheses. The second generates multiset permutations in linear space using only arrays;it is simpler and more efficient than the recent algorithm of Korsh & LaFollette.

关键词： fusing loopless algorithms parenthesis strings multiset permutations

来源：评论

学校读者我要写书评

暂无评论

loopless Generation of Non-regular Trees with a Prescribed Branching Sequence¹

引用

COMPUTER JOURNAL 2010年第6期53卷 661-666页

作者： Wu, Ro-Yu Chang, Jou-Ming Wang, Yue-Li Natl Taiwan Univ Sci & Technol Dept Informat Management Taipei Taiwan Natl Taipei Coll Business Dept Informat Management Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Tao Yuan Taiwan

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences.

关键词： non-regular trees coding trees gray-code generation loopless algorithms

来源：评论

学校读者我要写书评

暂无评论

Loop-Free Gray Code algorithms for the Set of Compositions

引用

Journal of Mathematical Modelling and algorithms 2010年第4期9卷 343-356页

作者： Mansour, Toufik Nassar, Ghalib Department of Mathematics University of Haifa 31905 Haifa Israel

The topic of Gray codes for the set of compositions with non-negative integer parts has been studied by several authors. Klingsberg gave a non-recursive description of a Gray code for this set after the recursive version of Knuth. Recently, Walsh modified Klingsberg's algorithm to find a Gray code which generates the set of all bounded compositions with non-negative integer parts. In this paper, we present two loopless Gray code algorithms for the set of compositions with positive integer parts. © 2010 Springer Science+Business Media B.V.

关键词： Compositions Gray codes loopless algorithms

来源：评论

学校读者我要写书评

暂无评论

Gray codes, loopless algorithm and partitions

引用

Journal of Mathematical Modelling and algorithms 2008年第3期7卷 291-310页

作者： Mansour, Toufik Nassar, Ghalib Department of Mathematics University of Haifa Haifa 31905 Israel

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth's algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n];Ruskey and Savage generalized Ehrlich's results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process. © 2008 Springer Science+Business Media B.V.

关键词： Gray codes loopless algorithms Partitions Plane trees

来源：评论

学校读者我要写书评

暂无评论

Three New Combination algorithms with the Minimal Change Property

引用

Communications of the ACM 1982年第8期25卷 555-559页

作者： Lam, Clement W. H. Soicher, Leonard H. Department of Computer Science Concordia University Montreal Quebec H3G IM8 1455 Maisonneuve Blvd West Canada University of Cambridge Department of Pure Mathematics and Mathematical Statistics Cambridge CB2 ISB England 16 Mill Lane United Kingdom

A combination is a k-subset of an n-set. Classical algorithms to generate all the combinations with the minimal change and loopless properties were usually complicated because they required special arrays in order to achieve the ioopless property. Three algorithms to generate combinations with the minimal change property are presented. The first one is obtained by making a simple change to the ordinary method of recursive generation of combinations in reverse lexicographical order. The second algorithm, which has the ioopless property, is obtained from the first one by using an ordinary stack to remove the recursion. The third algorithm is an optimized version of the second one. By timing comparisons, this final algorithm is considerably faster than the previously published combination algorithms, especially when k is small compared to n. © 1982, ACM. All rights reserved.

关键词： combinations loopless algorithms minimal change subsets

来源：评论

学校读者我要写书评

暂无评论

Combination Generators

引用

ACM Transactions on Mathematical Software (TOMS) 1979年第2期5卷 163-172页

作者： Payne, W.H. Ives, F.M. Computer Science Department Washington State University Pullman WA 99163 United States Mathematics and Computer Science Department Western Washington State University Bellingham WA 98225 United States

The Liu-Tang combmanon enumeration algonthm produces a cyclic sequence of combmations. Each combination is obtained from Its predecessor by a single exchange of two marks. History of the sequence does not need to be known to generate the next combmanon, A pointer programmed version of the LIU-Tang algonthm greatly improves fed of execution compared to the original coding when K or N - K IS small as they appear m \K). ThIS implementation was rated with respect to advantageous attributes and compared favorably with several other combination enumeration algorithms. © 1979, ACM. All rights reserved.

关键词： binomial and multinomial coefficients combmations constant-weight codes Hamiltonian CIrCUIts on the N-cube loopless algorithms permutations with repetitions permitted pointers

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：