Code covered by the BSD License  

Highlights from
Kautz sequence generator

Be the first to rate this file! 11 Downloads (last 30 days) File Size: 3.84 KB File ID: #31201

Kautz sequence generator

by

 

26 Apr 2011 (Updated )

Generates example Kautz sequences of specified number of characters and subsequence lengths.

| Watch this File

File Information
Description

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.

Acknowledgements

Combn (4.3) inspired this file.

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
27 Oct 2014 W. Owen Brimijoin

@memoly

This example you are showing here seems to me to be a legitimate 3^3 Kautz sequence. Could you explain why you've identified these particular substrings as incorrect?

The condition of the Kautz sequence is not that there be no repeated characters in a substring (in your case, each set of 3), rather that the sequence simply not contain any *consecutive* repeats of the same character.

25 Oct 2014 Memoly Memoly

For the example sequence generated like : 3 1 3 2 1 2 1 3 1 2 3 2

But is that correct?
313-wrong
132
321
212-wrong
121-wrong
213
131-wrong
312
123
232-wrong
323
231

Updates
29 Apr 2011

Title change

22 Jul 2011

Added acknowledgment to COMBN (jos)

Contact us