Generates example de Bruijn sequences of specified number of characters and subsequence lengths.
This function will compute an example of an interleaved pseudorandom de Bruijn sequence, a member of the larger class of Msequences. 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^(L1) examples of each character,
N^(L2) examples of each pair of characters,
N^(L3) 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).
1.3  edited description 

1.2  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  Edited description, added tags 
Owen Brimijoin (view profile)
@vinod
In its current form, no, there is no way to force it to generate all possible 4^2 sequences short of exhaustively running the function in a while loop and checking for unique results until all 16 are generated (not particularly efficient, to put it mildly).
vinod (view profile)
Using this code am i able to generate all debruijn sequences?........for example for n=4 and k=2,there are 16 debruijn sequences.
Owen Brimijoin (view profile)
@Mahdiyar  from the error you are getting, I'd guess that you haven't put the mfile in a directory that Matlab knows anything about. Either use addpath or place the file in your current directory and it should work just fine.
Mahdiyar (view profile)
I run the code attached at this page but it gives me the following error
>> sequence = debruijn_generator(3,2)'
Undefined function 'debruijn_generator' for input arguments of type
'double'.
Please let me know what should I do.
Owen Brimijoin (view profile)
@fan
It’s a bit of a needleinthehaystack problem. While it’s true there are many valid (k,n) de Bruijn sequences (this many: factorial(k)^(k*(n1))/k*n), there are k^(k^n) possible ways to combine k characters in a sequence of equal length!
This mfile keeps a *simple* history of deadends in its attempt to find a valid sequence, the simplicity of it being an advantage in avoiding outofmemory problems, but I do not doubt there are better ways to do it. Suggestions are most definitely appreciated!
Alex (view profile)
2Dkey 0011
000 0 Do
001 1 Re
011 2 Mi
111 3 Re
101 2
(1*sqrt(0)+1*sqrt(1)+2*sqrt(2)+1*sqrt(3))*2/4=pi
3Dkey 00010111
0000 0 Do
0001 1 Mi
0101 2 Re
0111 3 Mi
0011 2 Fa
1011 3 Re
1001 2 Mi
1101 3 Re
1111 4
(1*sqrt(0)+1*sqrt(1)+3*sqrt(2)+3*sqrt(3)+1*sqrt(4))*2/8=pi
5Dkey 00000101100100011101010011011111
000000 0 Do
000001 1 Mi
000101 2 Re
000111 3 So
010111 4 Fa
011111 5 Mi
011011 4 Re
011001 3 So
001001 2 Do
001000 1 Mi
001100 2 Fa
000100 1 So
010100 2 Re
010110 3 Mi
010010 2 Fa
011010 3 So
001010 2 La
101010 3 Fa
100010 2 So
110010 3 Re
110000 2 Mi
110100 3 Fa
111100 4 So
101100 3 Re
101110 4 La
001110 3 Fa
000110 2 Mi
000010 1 Re
000000 0 So
010000 1 Fa
011000 2 Mi
011100 3 Re
011110 4
(2*sqrt(0)+5*sqrt(1)+10*sqrt(2)+10*sqrt(3)+5*sqrt(4)+1*sqrt(5))*2/31=pi
fan (view profile)
I have another question.Since this function generates the requierd DB sequence through searching all the possible symbol combinations according to the character, arbitrary DB sequence can be obtained without regard to the limitaion of time and memory in principle. However, the generation of the sequence with large period is rather timing consuming. The command 'debruijn_generator(4,8)' gived no result after running for 8 hours. Any sugestions for this problem? Thank you very much.
Owen Brimijoin (view profile)
In principle you could reseed Matlab's random number generator to the same value each time:
rand('seed',0);
sequence1 = debruijn_generator(5,3)
rand('seed',0);
sequence2 = debruijn_generator(5,3)
These ought to be the same. On the other hand, there is no reason you could not simply save a given sequence and load it whenever you need it.
fan (view profile)
Thank you for author's kind sharing. But how to obtain the same DB sequence each time?