de Bruijn sequence generator

Generates example de Bruijn sequences of specified number of characters and subsequence lengths.
1.8K Downloads
Updated 22 Jul 2011

View License

This function will compute an example of an interleaved pseudo-random de Bruijn sequence, a member of the larger class of M-sequences. The sequence will contain an equal number of each character and subsequence of characters. The sequence is, by nature, circular, so the final members of pairs (or triplets, quadruplets, etc...) are found wrapped around to the beginning of the sequence.
Example:
>> sequence = debruijn_generator(3,2)'
sequence =
[1 2 1 3 3 2 2 3 1]

A sequence of N characters with a subsequence length of L would be
---------------------------------------------
N^L characters in length,and would contain:
N^(L-1) examples of each character,
N^(L-2) examples of each pair of characters,
N^(L-3) examples of each possible triplet of characters,
and so on.
---------------------------------------------

Computation times will be *considerable* and unpredictable for large numbers of characters (>10) and subsequence lengths (>4). Sometimes the code will be unable to compute a solution and will restart. This restart is initiated when the total computation time exceeds time taken before the first backtrack times a multiplier of 4 (arrived at empirically as the multiplier that results in the fastest average solution).

Revised: 14th July, 2010 - Changed method for permuting all possible combinations to that created by Jos van der Geest (combn.m available on File Exchange).

If you find this function useful and use it for experimental design, please consider citing Brimijoin and O'Neill, 2010 - (Hearing Research).

Cite As

W. Owen Brimijoin (2024). de Bruijn sequence generator (https://www.mathworks.com/matlabcentral/fileexchange/28015-de-bruijn-sequence-generator), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R14SP2
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Random Number Generation in Help Center and MATLAB Answers
Acknowledgements

Inspired by: permn

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.3.0.0

edited description

1.2.0.0

Improved help text (added H1 line), added more input error checking, and changed method for initially computing all possible combinations to that written by Jos van der Geest (combn.m available on File Exchange).

1.1.0.0

Edited description, added tags

1.0.0.0