We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes ...
详细信息
We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li (2012) [17]. We then introduce an iterative algorithm that generates the same rotation Gray codes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and O(n)- amortized time per string respectively, using a linear amount of memory.
Lists of equivalence classes of words under rotation or rotation plus reversal (i.e., necklaces and bracelets) have many uses, and efficient algorithms for generating these lists exist. In combinatorial group theory e...
详细信息
Lists of equivalence classes of words under rotation or rotation plus reversal (i.e., necklaces and bracelets) have many uses, and efficient algorithms for generating these lists exist. In combinatorial group theory elements of a group are typically written as words in the generators and their inverses, and necklaces and bracelets correspond to conjugacy classes and relators respectively. We present algorithms to generate lists of freely and cyclically reduced necklaces and bracelets in free groups. Experimental evidence suggests that these algorithms are cat – that is, they run in constant amortized time.
Bracelets are lexicographically minimal k-ary strings symmetric under rotation and reversal. In this paper, we present an algorithm for lexicographic listing of bracelets with fixed density. Our algorithm works for ar...
详细信息
Bracelets are lexicographically minimal k-ary strings symmetric under rotation and reversal. In this paper, we present an algorithm for lexicographic listing of bracelets with fixed density. Our algorithm works for arbitrarily large alphabet size and each successive bracelet is generated in constant amortized time.
A bracelet is the lexicographically smallest element in an equivalence class of strings under string rotation and reversal. We present a fast, simple, recursive algorithm for generating (i.e., listing) k-ary bracelets...
详细信息
A bracelet is the lexicographically smallest element in an equivalence class of strings under string rotation and reversal. We present a fast, simple, recursive algorithm for generating (i.e., listing) k-ary bracelets. Using simple bounding techniques, we prove that the algorithm is optimal in the sense that the running time is proportional to the number of bracelets produced. This is an improvement by a factor of n ( where n is the length of the bracelets being generated) over the fastest, previously known algorithm to generate bracelets.
We develop a fast algorithm for listing all necklaces with fixed content. By fixed content, we mean the number of occurrences of each alphabet symbol is fixed. Initially, we construct a simple but inefficient algorith...
详细信息
We develop a fast algorithm for listing all necklaces with fixed content. By fixed content, we mean the number of occurrences of each alphabet symbol is fixed. Initially, we construct a simple but inefficient algorithm by making some basic modifications to a recursive necklace generation algorithm. We then improve it by using two classic combinatorial optimization techniques. An analysis using straight forward bounding techniques is used to prove that the algorithm runs in constant amortized time. (C) 2003 Elsevier Science B.V. All rights reserved.
We refer to positive lattice paths as to paths in the discrete plane constituted by different kinds of steps (north-east, east and south-east), starting from the origin and never going under the x-axis. They have been...
详细信息
We refer to positive lattice paths as to paths in the discrete plane constituted by different kinds of steps (north-east, east and south-east), starting from the origin and never going under the x-axis. They have been deeply studied both from a combinatorial and an algorithmic point of view. We propose some algorithms for the exhaustive generation of positive paths which are Motzkin and Schroder paths and their prefixes, according to their length. For each kind of paths we define a recursive algorithm as well as an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of these algorithms by using the relations between the number of paths of a given size and the number of final north-east or south-east steps. (C) 2020 Elsevier B.V. All rights reserved.
A k-ary necklace is an equivalence class of k-ary strings under rotation. A necklace of fixed density is a necklace where the number of zeros is fixed. We present a fast, simple, recursive algorithm for generating (i....
详细信息
A k-ary necklace is an equivalence class of k-ary strings under rotation. A necklace of fixed density is a necklace where the number of zeros is fixed. We present a fast, simple, recursive algorithm for generating (i.e., listing) fixed-density k-ary necklaces or aperiodic necklaces. The algorithm is optimal in the sense that it runs in time proportional to the number of necklaces produced.
We present an algorithm to generate bracelets with fixed content. An analysis shows that the algorithm runs in constant amortized time. The algorithm can be applied to efficiently list all non-isomorphic unicyclic gra...
详细信息
We present an algorithm to generate bracelets with fixed content. An analysis shows that the algorithm runs in constant amortized time. The algorithm can be applied to efficiently list all non-isomorphic unicyclic graphs with n vertices. (C) 2012 Elsevier B.V. All rights reserved.
A hard real-time system is usually subject to stringent reliability and timing constraints since failure to produce correct results in a timely manner may lead to a disaster. One way to avoid missing deadlines is to t...
详细信息
A hard real-time system is usually subject to stringent reliability and timing constraints since failure to produce correct results in a timely manner may lead to a disaster. One way to avoid missing deadlines is to trade the quality of computation results for timeliness and software fault tolerance is often achieved with the use of redundant programs. A deadline mechanism which combines these two methods is proposed to provide software fault tolerance in hard real-time periodic task systems. Specifically, we consider the problem of scheduling a set of real-time periodic tasks each of which has two versions: primary and alternate. The primary version contains more functions (thus more complex) and produces good quality results, but its correctness is more difficult to verify because of its high level of complexity and resource usage. By contrast, the alternate version contains only the minimum required functions (thus simpler) and produces less precise, but acceptable results and its correctness is easy to verify. We propose a scheduling algorithm which 1) guarantees either the primary or alternate version of each critical task to be completed in time and 2) attempts to complete as many primaries as possible. Our basic algorithm uses a fixed priority-driven preemptive scheduling scheme to preallocate time intervals to the alternates and, at runtime, attempts to execute primaries first. An alternate will be executed only 1) if its primary fails due to lack of time or manifestation of bugs or 2) when the latest time to start execution of the alternate without missing the corresponding task deadline is reached. This algorithm is shown to be effective and easy to implement. this algorithm is enhanced further to prevent early failures in executing primaries from triggering failures in the subsequent job executions, thus improving efficiency of processor usage.
An indecomposable permutation pi on [n] is one such that pi([m]) = [m] for no m < n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to g...
详细信息
An indecomposable permutation pi on [n] is one such that pi([m]) = [m] for no m < n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (cat). We also present a cat generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open. (c) 2006 Elsevier B.V All rights reserved.
暂无评论