# 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?

/

#