• 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

See debruijnsequence.org to find implementations for a variety of de Bruijn sequence constructions.

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.