Generating de Bruijn Sequences
Agenda
Introduction
- Daan van Berkel
- Netherlands
- Luminis
Definition
a \(k\)-ary De Bruijn sequence \(B(k, n)\) of order \(n\) is a cyclic sequence of a given alphabet \(A\) with size \(k\) for which every possible subsequence of length \(n\) in \(A\) appears as a sequence of consecutive characters exactly once.
Example
With \(k =\) _ and \(n =\) _ the following sequence is a \(B(k, n)\) De Bruijn sequence over alphabet \(A =\) _.
_
Proof
Why is it a \(B(k, n)\) De Bruijn sequence for \(k =\) _ and \(n = \) _ over \(A =\) _
Why would you care
Generation
How to generate De Bruijn sequences
To generate a \(B(k,n)\) de Bruijn sequences one can execute the following algorithm.
- Generate all combinations of length \(n-1\)
- Connect a combinations \(w\) with \(w|l\) for each letter \(l\)
- Find an Eulerian Cycle
- Read off the edge labels
With \(k =\) _, \(n =\) _ and alphabet \(A =\) _.
Code
Pair up and get started!
- Check-out a branch
- Read the README.md
- Enjoy yourself
Questions?
/
#