image thumbnail

Kautz sequence generator

version 1.3.0.0 (3.84 KB) by W. Owen Brimijoin
Generates example Kautz sequences of specified number of characters and subsequence lengths.

499 Downloads

Updated 22 Jul 2011

View License

The Kautz sequence is of the same family of sequences as the de Bruijn sequence, but has an additional requirement that it not contain any consecutive repeats of the same character.

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 = kautz_generator(3,3)'

sequence =
3 1 3 2 1 2 1 3 1 2 3 2

A sequence of N characters with a subsequence length of L would be
---------------------------------------------
N*(N-1)^(L-1)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).

If you find this useful and use it for research, please cite:
Brimijoin WO, McShefferty D, Akeroyd MA. J Acoust Soc Am. 2010 Jun;127(6):3678-88.

Cite As

W. Owen Brimijoin (2022). Kautz sequence generator (https://www.mathworks.com/matlabcentral/fileexchange/31201-kautz-sequence-generator), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired by: permn

Community Treasure Hunt

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

Start Hunting!