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.



Selected citations:
Back to list of publications.