We show how the arithmetic structure of the set of borders (periods) of a word can be used to substantially reduce complexity of an interesting problem in combinatorics on words. A word w is a bordered word if it has ...
详细信息
ISBN:
(纸本)9783031721991;9783031722004
We show how the arithmetic structure of the set of borders (periods) of a word can be used to substantially reduce complexity of an interesting problem in combinatorics on words. A word w is a bordered word if it has a non-empty proper border (a prefix which is a suffix);equivalently, it has a period smaller than |w|. Words which are not bordered are called unbordered. The problem of ranking/unranking such words of a given length n over an alphabet of size k was considered by Gabric (Inf. Process. Lett., 2024). We improve his results as follows: complexity of ranking is reduced by a factor nk/ log n and complexity of unranking by n(2) k/log n (for large alphabets these improvement factors are n(2)/log n and n(3)/log n, respectively). We use the unit-cost RAM model (the same model was used by Gabric).
In the context of combinatorial sampling, the so-called "unranking method" can be seen as a link between a total order over the objects and an effective way to construct an object of given rank. The most cla...
详细信息
In the context of combinatorial sampling, the so-called "unranking method" can be seen as a link between a total order over the objects and an effective way to construct an object of given rank. The most classical order used in this context is the lexicographic order, which corresponds to the familiar word ordering in the dictionary. In this article, we propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations, including three algorithms that were introduced decades ago. We start the paper with the introduction of our new algorithm using a new strategy of computations based on the classical factorial numeral system (or factoradics). Then, we present, in a high level, the three other algorithms. For each case, we analyze its time complexity on average, within a uniform framework, and describe its strengths and weaknesses. For about 20 years, such algorithms have been implemented using big integer arithmetic rather than bounded integer arithmetic which makes the cost of computing some coefficients higher than previously stated. We propose improvements for all implementations, which take this fact into account, and we give a detailed complexity analysis, which is validated by an experimental analysis. Finally, we show that, even if the algorithms are based on different strategies, all are doing very similar computations. Lastly, we extend our approach to the unranking of other classical combinatorial objects such as families counted by multinomial coefficients and k-permutations.
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 c...
详细信息
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).
暂无评论