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 suction and operation parameters remarkably influence the performance and efficiency of the pumping unit system, the theoretical and experiential model selection methods being verified to be not effective on param...
详细信息
ISBN:
(数字)9783319520155
ISBN:
(纸本)9783319520155;9783319520148
The suction and operation parameters remarkably influence the performance and efficiency of the pumping unit system, the theoretical and experiential model selection methods being verified to be not effective on parameters adoption. The fkm cluster algorithm model selection is put forward to deal with huge data processing in model selection, the efficiency curves comparison indicates: the pumping unit model selection on a oilfield block keep more stable and higher efficiency. The efficiency membership to operation parameters combination is revealed to be the approach to best performance and high efficiency. The reasonable match of equipment and process saves power rather than pure equipment.
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 <
H. Fredricksen, I. J. Kessler and J. Maiorana discovered a simple but elegant construction of a universal cycle for binary strings of length n: Concatenate the aperiodic prefixes of length n binary necklaces in lexico...
详细信息
H. Fredricksen, I. J. Kessler and J. Maiorana discovered a simple but elegant construction of a universal cycle for binary strings of length n: Concatenate the aperiodic prefixes of length n binary necklaces in lexicographic order. We generalize their construction to binary strings of length n whose weights are in the range c, c + 1,..., n by simply omitting the necklaces with weight less than c. We also provide an efficient algorithm that generates the universal cycles in constant amortized time per bit using O(n) space. Our universal cycles have the property of being the lexicographically smallest universal cycle for the set of binary strings of length n with weight >= c. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论