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 k-ary necklace is an equivalence class of k-ary strings under rotation (the cyclic group). A k-ary unlabeled necklace is an equivalence class of k-ary 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) 267-282.
The algorithms are used in the Combinatorial Object Server (COS) in the sections for generating necklaces and irreducible polynomials.
Kevin Cattell was working for Hewlett-Packard 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 variable-length 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. 23-35, 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 187-197. Birkhäuser Verlag, 2004.

Back to list of publications.