Generating a sequence

I'm trying to generate a DeBrujin sequence using MATLAB.

    Set x(1), x(2) ... x(n) = 0

    Set i = n + 1

    While i <= 2^n

    Set z = the opposite of x(i‐1) (i.e. if x(i‐1) is a zero then z = 1 and vice versa).

    Test if adding z to the end of the sequence produces a pattern of length n at the end of the sequence that already appears somewhere in the sequence.

    If the pattern already appears then set z = x(i‐1).

    Add z to the end of the sequence (i.e. set x(i) = z),

    Increment i

The above is the pseudocode for what I'm trying to make. Disregarding the step where I check if the pattern appears, I've made the following code.

function [sequence] = DeBrujin (order)
%debrujinGen

sequence (1:order) = 0;

for sequence = 1:order
    i = order + 1;
    while i <= (2.^order)
        if sequence(i-1) == 0
            z = 1;
        else z = 0;
        end
        sequence(i) = z;
        i = i + 1;
    end
end
return

I have been trying to debug this code but keep coming across the following error:

>> [sequence] = DeBrujin (3)
??? Index exceeds matrix dimensions.

Error in ==> DeBrujin at 9
        if sequence(i-1) == 0

What am I doing wrong here? Thanks.

Answer 1

[Fangjun Jiang]

Why do you have the for-loop? Based on your pseudo code, it should be:

function [sequence] = DeBrujin (order)
%debrujinGen
sequence (1:order) = 0;
    i = order + 1;
    while i <= (2.^order)
        if sequence(i-1) == 0
            z = 1;
        else z = 0;
        end
        sequence(i) = z;
        i = i + 1;
    end

One more thing, 2^n is much larger than n. It's better to pre-allocate sequence(1:2^n)=0