1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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

0

Reset to default

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.