Code covered by the BSD License

### Highlights from de Bruijn sequence generator

Be the first to rate this file! 13 Downloads (last 30 days) File Size: 3.66 KB File ID: #28015 Version: 1.3

# de Bruijn sequence generator

### Owen Brimijoin (view profile)

25 Jun 2010 (Updated )

Generates example de Bruijn sequences of specified number of characters and subsequence lengths.

File Information
Description

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).

Acknowledgements

Permn(V, N, K) inspired this file.

MATLAB release MATLAB 7.0.4 (R14SP2)
17 Sep 2014 Owen Brimijoin

### 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).

Comment only
17 Sep 2014 vinod

### 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.

Comment only
29 May 2013 Owen Brimijoin

### Owen Brimijoin (view profile)

@Mahdiyar - from the error you are getting, I'd guess that you haven't put the m-file 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.

Comment only
24 May 2013 Mahdiyar

### 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.

Comment only
19 Aug 2011 Owen Brimijoin

### Owen Brimijoin (view profile)

@fan

It’s a bit of a needle-in-the-haystack problem. While it’s true there are many valid (k,n) de Bruijn sequences (this many: factorial(k)^(k*(n-1))/k*n), there are k^(k^n) possible ways to combine k characters in a sequence of equal length!

This m-file keeps a *simple* history of dead-ends in its attempt to find a valid sequence, the simplicity of it being an advantage in avoiding out-of-memory problems, but I do not doubt there are better ways to do it. Suggestions are most definitely appreciated!

Comment only
16 Aug 2011 Alex

### Alex (view profile)

2D-key 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

3D-key 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

5D-key 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

Comment only
29 Jul 2011 fan

### 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.

Comment only
29 Jun 2011 Owen Brimijoin

### 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.

Comment only
01 May 2011 fan

### fan (view profile)

Thank you for author's kind sharing. But how to obtain the same DB sequence each time?

Comment only
28 Jun 2010 1.1