𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A fast algorithm to generate necklaces with fixed content

✍ Scribed by Joe Sawada

Book ID
104325765
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
230 KB
Volume
301
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We develop a fast algorithm for listing all necklaces with ΓΏxed content. By ΓΏxed content, we mean the number of occurrences of each alphabet symbol is ΓΏxed. Initially, we construct a simple but ine cient algorithm by making some basic modiΓΏcations to a recursive necklace generation algorithm. We then improve it by using two classic combinatorial optimization techniques. An analysis using straight forward bounding techniques is used to prove that the algorithm runs in constant amortized time.

πŸ“œ SIMILAR VOLUMES

Fast Algorithms to Generate Necklaces, U
Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)
✍ Kevin Cattell; Frank Ruskey; Joe Sawada; Micaela Serra; C.Robert Miers πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 114 KB

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