Generating Necklaces and Strings with Forbidden Substrings
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Given a length m string f over a kary alphabet
and a positive integer n, we develop efficient algorithms to
generate

all kary strings of length n that have no
substring equal to f,

all kary circular strings of length n that have
no substring equal to f, and

all kary necklaces of length n that
have no substring equal to f,
where f is an aperiodic necklace.
Each of the algorithms runs in amortized time O(1) per string
generated, independent of k, m, and n.


Presented at the 6th Annual International Combinatorics and
Computing Conference (COCOON), Bondi Beach, Australia,
Lecture Notes in Computer Science, #1858 (2000) 330339.

Selected Citations to this paper:

P. Flener and J. Pearson,
Solving Necklace Constraint Problems,
Journal of Algorithms: Cognition, Informatics and Logic,
to appear, 2008.
Back to list of publications.