Generating Necklaces
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Carla Savage,
Department of Computer Science,
North Carolina State University, USA.
Terry MinYih Wang,
Department of Computer Science,
North Carolina State University, USA.
Abstract:
A k-color, n-bead necklace is an equivalence class
of k-ary n-tuples under rotation.
In this paper, we analyze an algorithm due to Fredricksen, Kessler,
and Maiorana (FKM), to show that necklaces can be generated in constant
average time.
We also present a new approach to generating necklaces which we
conjecture can be implemented in constant worst case time.
The FKM algorithm generates a list of n-tuples which includes,
among other things, the lexicographically smallest element of each
k-color, n-bead necklace.
Previously it had been shown only that the list contains
at most O(n·N(k,n))
elements, where N(k,n) is the number of
k-color, n-bead necklaces, and that
successive elements can be generated in worst case time
O(n), giving a bound of
O(n2·N(k,n))
on the time for the algorithm.
We show that the number of elements generated by the FKM algorithm
approaches (k/(k-1))·N(k,n)
and the total time is only O(N(k,n)).
A by-product product of our analysis is a precise characterization of the
list generated by FKM, which makes a recursive description possible.
-
The postscript file is 202,777 bytes,
the dvi file is 55,408 bytes.
-
Appeared in Journal of Algorithms 13 (1992) 414-430.
-
If anybody knows the current whereabouts of Terry Wang please
let me know.
-
If you want to generate necklaces online, visit
COS the combinatorial
object server.
Selected citations:
-
Christopher Degni and Arthur A. Drisko
Gray-ordered Binary Necklaces,
Electronic Journal of Combinatorics, paper R7 (Jan 3, 2007),
23 pages.
-
Eduardo Moreno and Martín Matamala,
Minimal de Bruijn Sequence in a Language with Forbidden Substrings,
Graph-Theoretic Concepts in Computer Science,
Lecture Notes in Computer Science, 3353 (2004) 168-176.
-
S. Chastel and D. Paulus,
Texture Identification Using Image Neighborhood Hypergraphs,
SPIE, San Jose, 2004.
-
John Ellis and Minko Markov,
In situ, Stable Merging by Way of the Perfect Shuffle,
The Computer Journal, 43 (2000) 40-53.
-
Moshe Schwartz and Tuvi Etzion,
The Structure of Single-Track Gray Codes,
IEEE Transactions on Information Theory,
45, November 1999, 2383-2396.
Back
to list of publications.
