I have recently discovered a greedy algorithm to construct De Bruijin Sequence. The greedy approach (prefer-largest specifically) works like the following:

  1. Start with a sequence of all 0's of length n - 1 where n is the order of De Bruijin Sequence.
  2. For k^n times (where 0...k-1 are the possible digits in the strings in the sequence), check from k - 1 to 0 (always try to append the largest digit) to see if the last n substring of the currently built sequence is a unique combination (this is kept track of using a set)

I have implemented this and it works but my question is WHY DOES IT WORK? I don't have master's in algorithms or math so if you can explain this in relatively plain terms, I would really appreciate it

  • $\begingroup$ I think the easiest answer is that you're using a set to keep track of unique combinations. Because of this operation, you ensure that you will never create a duplicate in the sequence. In other words, when you "check...to see if the last n substring...is a unique combination", you have effectively ensured that you will never add a duplicate. The only other problem that may occur is that you don't add all $k^n$ sequences, which won't happen because you go through $k^n$ sequences, which are all that are required. $\endgroup$
    – Matt Groff
    Mar 8 at 4:12
  • $\begingroup$ The key here is that you always to try to append the highest digit to the sequence. If you try to append from 0, you will end up with a wrong sequence. It's almost like magic. This is the part I am having a really hard time understanding or finding out why $\endgroup$
    – BSE10
    Mar 9 at 13:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.