Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert at the end if there is no remaining 10. Do it again. And again. Keep going! Eventually, you will cycle ...
详细信息
Pick a binary string of length n and remove its first bit b. Now insert b after the first remaining 10, or insert at the end if there is no remaining 10. Do it again. And again. Keep going! Eventually, you will cycle through all 2 (n) of the binary strings of length n. For example, are the binary strings of length n=4, where and . And if you only want strings with weight (number of 1s) between a"" and u? Just insert b instead of when the result would have too many 1s or too few 1s. For example, are the strings with n=4, a""=0 and u=2. This generalizes 'cool-lex' order by Ruskey and Williams (The coolest way to generate combinations, Discrete Mathematics) and we present two applications of our 'cooler' order. First, we give a loopless algorithm for generating binary strings with any weight range in which successive strings have Levenshtein distance two. Second, we construct de Bruijn sequences for (i) a""=0 and any u (maximum specified weight), (ii) any a"" and u=n (minimum specified weight), and (iii) odd u-a"" (even size weight range). For example, all binary strings with n=6, a""=1, and u=4 appear once (cyclically) in . We also investigate the recursive structure of our order and show that it shares certain sublist properties with lexicographic order.
The cyclic sequence 0000100110101111 has the unlikelyproperty that the 16 unique binary substrings of length 4 appearexactly once in the sequence as a substring. This sequence is anexample of a universal cycle. A univ...
详细信息
The cyclic sequence 0000100110101111 has the unlikelyproperty that the 16 unique binary substrings of length 4 appearexactly once in the sequence as a substring. This sequence is anexample of a universal cycle. A universal cycle for an arbitraryset S is a cyclic sequence of length |S| whose substrings of lengthn encode |S| distinct instances in S. When S is the set of k-arystrings of length n, these sequences are commonly studied under thename de Bruijn sequence. Universal cycles have been studied fora wide variety of combinatorial objects including permutations,partitions, subsets, multisets, labeled graphs, various functionsand passwords. The study of universal cycles has a long historywith applications including dynamic connections in overlaynetworks, genomics, software calculation of the ruler function incomputer words, and indexing a 1 in a computer word. There arestandard proofs to demonstrate the existence of universal cyclesfor a variety of combinatorial objects; however, only a smallnumber of universal cycles can be constructed efficiently andpractically. This thesis provides novel efficient constructions togenerate universal cycles for a variety of combinatorial objects. Our research leads to several new results. Firstly, we propose anovel shift rule to construct de Bruijn sequence for length nbinary strings. The shift rule provides a simple and efficientsuccessor rule to find the next bit in the de Bruijn sequence andis applicable to all values of n. We then extend the shift rule toconstruct de Bruijn sequence for k-ary strings of length ***, we generalize the Fredricksen-Kessler-Maiorana (FKM)construction and Greedy construction to generate universal cyclesfor a broad class of k-ary strings. We also prove that theuniversal cycles produced are the lexicographically smallest forthe sets. Lastly, we provide the first known efficient constructionto generate universal cycles for length n binary strings where thenumber of 1s range from c to d given 0 <
暂无评论