| |
If this code is useful in your research or applications, I would much appreciate knowing how they were used. Please let me know by sending email to: jsawada@uoguelph.ca . Applications for these and related algorithms include:
- 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 and relatives
necklaces.c:
generates necklaces and Lyndon words over an alphabet of size k in constant amortized time:
| • unrestricted | • bracelets
| | • fixed-density | • unlabeled (binary only)
| | • fixed-content | • chord diagrams
| | • Lyndon brackets (basis for free lie algebra)
|
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
|
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. Also, fixed density
de Bruijn cycles can be generated in constant time for each n bits generated.
|
| |
|
