
If this code is useful in your research or applications, I would much appreciate knowing how is is used. Please let me know by sending email to: jsawada@uoguelph.ca . Applications for these and related algorithms include:
 pseudorandom number generators
 construction of quantum errorcorrecting codes
 scoring patterns for musical pieces
 dynamical systems: the periodic orbits of the
chaotic baker map are in bijection with binary necklaces
 symmetry breaking while traversing a search tree of a constraint satisfaction problem
 lossless data compression
techniques
Necklaces, Lyndon words, De Bruijn sequences and relatives
debruijn_successors.c:
constructs eight unique binary de Bruijn sequences via successor rules. Each construction runs in O(n) time per bit except for the Huang sequence.
• Granddaddy (lexleast)  • Grandmama
 • Wong  • Williams
 • Gabric  • Sawada
 • S2  • Huang

necklaces.c:
generates necklaces and Lyndon words over an alphabet of size k, most in O(1)amortized time:
• unrestricted  • unlabeled (binary)
 • fixeddensity  • bracelets
 • fixedcontent  • charm bracelets
 • chord diagrams  • Lyndon brackets (basis for free lie algebra)
 • de Bruijn sequence  • with a forbidden subtring

neck_db.c:
generates fixed density necklaces, Lyndon words and pseudonecklaces in either coollex Gray code order or colex order.
All necklaces, Lyndon words, and pseudonecklaces can be generated in Gray code order by increasing density. Fixed density
de Bruijn sequences can be generated in constant time for each n bits generated.
ranking_necklaces.c:
ranks and unranks necklaces, Lyndon words and de Bruijn sequences over the alphabet {1,2,..., k}. Also computes the number of necklaces or Lyndon words with a given prefix.
ranking_fixed_density_necklaces.c:
ranks and unranks binary fixeddensity necklaces and Lyndon words. Also computes the largest fixed density necklace that is less than or equal to a given string.
Meanders, semimeanders, and stamp foldings
stamp.c:
generates the following objects using a permutation representation:
• open meanders  • symmetric meanders
 • semimeanders  • symmetric semimeanders
 • stamp foldings  • unlabeled stamp foldings

Bubble languages
all_bubble.c:
generates the following binary bubble languages in either coollex Gray code order or colex order. Each fixeddensity object can
be generated in constant amortized time.
• combinations  • ≥ reversal
 • forbidden 01^k or 10^k  • ≥ complemented reversal
 • ≤ k inversions  • ≤ k transpositions to sort
 • k largest strings  • kary Dyck words
 • necklaces  • connected unit interval graphs
 • Lyndon words  • solutions to knapsack with k items
 • linear extensions of Bposet  • ordered forests with ≤ k trees

Signed and unsigned permuations (Burnt and unburnt pancakes)
complete_pancake.c:
generates (signed) permutations in Gray code order based on either a greedy maximum or minimum flip strategy. The algorithms are implemented to run in O(1)amortized time. Efficient ranking and unranking algorithms for these listings are also provided.


