An Efficient Algorithm for Generating Necklaces with Fixed Density
(full paper)
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!
-
Appeared in SIAM J. Computing, 29 (1999) 671-684.
-
A
ten page abstract was presented at SODA 1999
(ACM/SIAM 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.
-
Typos in the SIAM J. Computing paper (publishers fault):
-
On page 675, the expression should be
at-p+1 + ap.
-
On page 676, the 6th line of the program the equal sign
= should be a colon-equal
:=.
-
On page 676, line 4 of the text the font in Gen2(t,p) should be
italic for t and p.
Selected Citations:
-
D. Baowan, B.J. Cox, and J.M. Hill,
Junctions between a boron nitride nanotube and a boron nitride sheet,
Nanotechnology, 19 (2008) (12 pp.).
-
Christopher Degni and Arthur A. Drisko,
Gray-ordered Binary Necklaces,
Electronic Journal of Combinatorics, Paper R7 (Jan 3, 2007) 23 pages.
-
David Rappaport,
Musical Scales, Integer Partitions, Necklaces, and Polygons,
9th ANNUAL INTERNATIONAL CONFERENCE OF BRIDGES:
Mathematical Connections in Art, Music, and Science.
London, England, Aug. 4 - August 9, 2006 pp. 595--598.
-
S. Chastel and D. Paulus,
Texture Identification Using Image Neighborhood Hypergraphs,
SPIE, San Jose, 2004.
Back to list of publications.