Generating de Bruijn Sequences

Agenda

Introduction

You are never to young to start learning TDD

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.

  1. Generate all combinations of length \(n-1\)
  2. Connect a combinations \(w\) with \(w|l\) for each letter \(l\)
  3. Find an Eulerian Cycle
  4. Read off the edge labels

With \(k =\) _, \(n =\) _ and alphabet \(A =\) _.

Code

Pair up and get started!

  1. Check-out a branch
  2. Read the README.md
  3. Enjoy yourself

Questions?

/

#