# Generating de Bruijn Sequences

## 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 =$$ _

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