Universal Cycles for Weight-Range Binary Strings

摘要

We present an efficient universal cycle construction for the set of binary strings of length n with weight (number of 1 s) in the range c,c+ 1,..., d where 0 ≤ c ＜ d ≤ n. The construction is based on a simple lemma for gluing universal cycles together, which can be implemented to generate each character in constant amortized time using O(n) space. The Gluing lemma can also be applied to construct universal cycles for other combinatorial objects including passwords and labeled graphs.