Fixed-Weight de Bruijn Cycles
Aaron Williams.
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Let Wn,w be the set of length n binary strings
containing w 1s and n-w 0s, and let
S{n}{w} = W{n-1}{w} U W{n-1}{w-1}.
We show that there is a universal cycle U{n}{w}
for S{n}{w}; that is, U{n}{w} is a circular binary string
of length ${n \choose w}$ that contains
each string in S{n}{w} as a substring.
Furthermore, U{n}{w} can be generated by an algorithm that uses
space O(n) and amortized time O(1) per bit of U{n}{w}.
This universal cycle may be viewed as a fixed weight analogue of
the classical de Bruijn cycle where the last (redundant) bit
from each string in $\mathbf{B}(n,w)$ is omitted.
Two consequences of our result are that there is a universal
cycle for the ``middle-two levels" of the Boolean lattice and that there is a
Gray code for $\mathbf{B}(n,w)$ in which successive binary strings
differ by $\sigma_n$ or $\sigma_{n-1}$, where
$\sigma_k$ is the result of the permutation $(k\ \cdots 2\ 1)$ acting
on the indices of the string.
Every string $\s$ may be written uniquely in the form $\mathbf{p}^k$, where
$\mathbf{p}$ is aperiodic; k is called the \emph{period} of the string.
We also show that there are universal cycles
(a) U+{n}{w}$ and (b) U-{n}{w}
for S{n}{w} in which every string appears (a) a number of times equal
to its period and (b) only if it is aperiodic.
-
The postscript file.
-
The pdf file.
-
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.
-
Selected citations:
Back to list of publications.
