Question

I dont know how to make de bruijn sequence in python. We have to print output by following this step.

1.start with a string of n consecutive zeroes

2.append 1 to the end of the string if the n-digit suffix that would be formed this way has not already appeared in the sequence; otherwise a 0 is appended to the end of the string.

3.repeat step 2 until the length of the sequence equals 2 **n

For instance, when we put input 4, we have to print output 0000111101100101

Solve me this question in pycharm... and please show the code.

Answer 1

Here is one of the simplest code for generating the de-bruijn sequence. I am attaching the code below with some screenshots of the output.

Although, for the input 4, my code is generating the output string having the same number of zeroes and one's as that you give in your question but the order is not preserved, but you should not worry about that because we can have more than one bruijn sequence for a given input.

Code :

def de_bruijn(d, n):
pos_seq = [0 for _ in range(n)]
l = 1
de_bruijn_seq = []
while True:
if n % l == 0:
de_bruijn_seq.extend(pos_seq[0:l])
for i in range(l, n):
pos_seq[i] = pos_seq[i-l]
l = n
while l > 0 and pos_seq[l-1] >= d-1:
l-=1
if l == 0:
break
pos_seq[l-1] += 1
return de_bruijn_seq
  
st = de_bruijn(2,4)
for i in st:
print(i, end="")

Screenshots :

​​​​​​

Explanation :

1. pos_seq will have the all posible type of subsequence of size n for the given d

2. de_bruijn_seq will store the de_bruijn seq and return it to the calling function where we store it's value in a var st

3. var l is acting as a pointer to move between the sequence

4. We only store a pos_seq in de_bruijn_seq, when n%l becomes zero

5. We break out of the loop when l becomes zero

6. At last we print our de_bruijn sequence using a for loop