J O E     S A W A D A
[   Home   ] [   Publications and Research   ] [   Algorithm Code   ]
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 error-correcting 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 (lex-least) • 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)
• fixed-density • bracelets
• fixed-content • 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 pseudo-necklaces in either cool-lex Gray code order or co-lex order. All necklaces, Lyndon words, and pseudo-necklaces 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 fixed-density necklaces and Lyndon words. Also computes the largest fixed density necklace that is less than or equal to a given string.

Meanders, semi-meanders, and stamp foldings

stamp.c: generates the following objects using a permutation representation:
• open meanders • symmetric meanders
• semi-meanders • symmetric semi-meanders
• stamp foldings • unlabeled stamp foldings

Bubble languages

all_bubble.c: generates the following binary bubble languages in either cool-lex Gray code order or co-lex order. Each fixed-density 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 • k-ary Dyck words
• necklaces • connected unit interval graphs
• Lyndon words • solutions to knapsack with k items
• linear extensions of B-poset • 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.