A fast algorithm to generate unlabeled necklaces
A fast algorithm to generate unlabeled necklaces
复制标题
生成未标记项链的快速算法
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. Sawada
中科院分区：
文献类型：
--
作者：
F. Ruskey;J. Sawada
抽象许多应用程序要求详尽的字符串列表受到各种限制，例如在小组行动下的不等值。 K-ary项链是旋转（循环基团）的k- ary弦的等效类别。 K-ary未标记的项链是在旋转和字母符号置换下的kary字符串等效类别。我们提出了用于生成（即清单）所有项链和二进制未标记项链的新的，快速，简单，递归的算法。对于固定t，对不发生substring 0 t的情况进行了概括。这些算法具有最佳的运行时间，因为它们的运行时间与产生的项链数量成正比。用于生成项链的算法可以用作有效生成旋转下许多其他等效字符串类别的基础，并已应用于产生手镯，固定密度项链和不可减少的多项式。
Abstrac t 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 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. These algorithms have optimal running times in the sense that their running times are proportional to the number of necklaces produced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rotation, and has been applied to generating bracelets, fixed density necklaces, and irreducible polynomials.