I have recently discovered a greedy algorithm to construct De Bruijin Sequence. The greedy approach (prefer-largest specifically) works like the following:
- Start with a sequence of all 0's of length n - 1 where n is the order of De Bruijin Sequence.
- 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