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

De Bruijn sequences

db_successors.c: constructs seven unique binary de Bruijn sequences via O(n) successor rules using O(n) space. Four are based on the PCR including the lexicographically smallest de Bruijn sequence (the Granddaddy) and three are based on the CCR.

db_greedy.c: constructs four unique k-ary de Bruijn sequences based on four greedy approaches:
• prefer-smallest
• prefer-largest
• prefer-same
• perfer-opposite
A major drawback of these algoritms is the requirement of O(kn) memory.

Necklaces, Lyndon words, and relatives

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 01k or 10k • ≥ 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

Unsigned, signed, or coloured permuations via prefix-reversals

coloured_permutations.c: generates (signed) permutations in Gray code order based on either a greedy maximum or minimum flip strategy. The minimum flip strategy is also extended to the more general coloured permutations. The algorithms are implemented to run in O(1)-amortized time. Efficient ranking and unranking algorithms, along with successor rules for these listings are also provided.