Generating Unlabelled Necklaces and Irreducible Polynomials over GF(2)
Kevin Cattell,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
C. Robert Miers,
Department of Mathematics and Statistics,
University of Victoria, Canada.
Micaela Serra,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Many applications call for exhaustive lists of strings subject to
various constraints, such as inequivalence under group actions.
A kary necklace is an equivalence class of kary strings
under rotation (the cyclic group).
A kary unlabeled necklace is an equivalence class of
kary strings under rotation and permutation of alphabet symbols.
We present new, fast, simple, recursive algorithms for generating
(i.e., listing) all necklaces and binary unlabeled necklaces.
Generalization is made to the case where no substring
0^{t} occurs, for fixed t.
All these algorithms have optimal running times in the sense that
their running times are proportional to the number of
necklaces produced.
As an application, we describe the implementation of a fast algorithm
for listing all degree n irreducible and primitive polynomials over
GF(2).

The postscript file is 236,341 bytes,
the dvi file is 70,800 bytes.

Appears in Journal of Algorithms, 37 (2000) 267282.

The algorithms are used in the Combinatorial Object Server
(COS) in the sections
for generating necklaces and irreducible polynomials.

Kevin Cattell was working for HewlettPackard in Santa Rosa, California,
but he is now at ??? in Vancouver.

Selected citations to this paper:

Jorg Arndt,
Matters Computational,
(Book) Springer, 2011.

T.A. Gulliver and U. Speidel,
A secure authentication system based on variablelength codes,
Information Theory and its Applications (ISITA),
2010 International Symposium on.

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

Petteri Kaski, Patric R. J. Ostergard,
Classification algorithms for codes and designs,
(Book), Springer, 2006.

Masanori Arita, Writing Information into DNA,
Aspects of Molecular Computing, LNCS 2950, pp. 2335, 2004.

C. Martínez and X. Molinero. An efficient generic algorithm for the
generation of unlabelled cycles. In M. Drmota, Ph. Flajolet, D. Gardy,
and B. Gittenberger, editors, Proc. of the 3rd Col. on Mathematics and
Computer Science: Algorithms, Trees, Combinatorics and Probabilities (MathInfo),
Trends in Mathematics, pages 187197. Birkhäuser Verlag, 2004.
Back to list of publications.