## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 31-40 |

Number of pages | 10 |

Journal | Journal of Discrete Algorithms |

Volume | 28 |

DOIs | |

Publication status | Published - Sept 2014 |

Externally published | Yes |

## Keywords

- De Bruijn cycle
- FKM algorithm
- Minimum weight
- Necklace
- Universal cycle