Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2)(1)

Many applications call for exhaustive lists of strings subject to various c onstraints, 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 rot ation and permutation of alphabet symbols. We present new, fast, simple, re cursive algorithms for generating (i.e., listing) all necklaces and binary unlabeled necklaces. These algorithms have optimal running times in the sen se that their running times are proportional to the number of necklaces pro duced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rota tion and has been applied to generating bracelets, fixed density necklaces, and chord diagrams. As another application, we describe the implementation of a fast algorithm for listing all degree n irreducible and primitive pol ynomials over GF(2). (C) 2000 Academic Press.