An Efficient Algorithm for Generating Necklaces with Fixed Density
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
A k-ary necklace is an equivalence class of
k-ary strings
under rotation.
A necklace of fixed density is a necklace where the number of
zeroes is fixed.
We present a fast, simple, recursive algorithm for generating
(i.e., listing) fixed density k-ary necklaces or
aperiodic necklaces.
The algorithm is optimal in the sense that it runs in time proportional
to the number of necklaces produced.
-
The postscript file is 166669 bytes,
the dvi file is 38,740 bytes.
Please send me a note
if you download a copy -- Thanks!
-
Accepted for presentation and long abstract at
SODA 1999 (Symposium on Discrete Algorithms).
-
The algorithms have been implemented and are used as the basis of the
online necklace generation algorithms of
COS,
the Combinatorial Object Server, in the section on
generating
necklaces.
Back to list of publications.