0 0 0 1 0 1 1 1

0

0 0 1

0 1 1

1

Example: A de Bruijn sequence with k=10 and n=4 is a minimal sequence to type for testing all the possible (code) sequences of length 4 on a device with 10 keys (labelled 0 to 9), and there are no restriction that you have to type Enter after each try. Click here to see that sequence. See the URL:s below for somewhat more serious applications...

For more information about these types of sequences see e.g.

- http://mathworld.wolfram.com/deBruijnSequence.html,
- http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html

See also:

- de Bruijn Applet, a Java Applet using the same approach as this program
- de Bruijn arbitrary sequences which generates sequences of "arbitrary" length
- de_bruijn.frink: implementation in the programming language Frink (se my Frink page for more info about the language)
- de_bruijn2.frink: implementation in the programming language Frink, similar to de_bruijn.frink but using OOP (and some extra features).
- There is also a couple of other implementations using Constraint Programming which makes it possible to generate
**all**possible solutions for a configuration (i.e. some specific`n`

and`k`

). These implements both the "standard" version and also the "arbitrary" variant, where the length of the sequence can be specified.

Some of these models where discussed in the blog post de Bruijn sequences in Gecode (and other systems). (Implementing de Bruijn sequences is a standard problem when I try out a new Constraint Programming system.)- debruijn_binary.mzn, a model in MiniZinc Constraint Programming language.
- debruijn_binary.zinc, a model in Zinc Constraint Programming language (a superset of the MiniZinc system).
- DeBruijn.java, a model in JaCoP, (a Java based) constraint programming language
- DeBruijn.scala a model in JaCoP/Scala
- DeBruijn.java, a model in Choco constraint programming language (Java)
- debruijn_binary.rb, a model in Gecode/R constraint programming language (Ruby interface to Gecode)
- debruijn.co, a model in Comet another constraint programming language
- debruijn.cpp, a model in Gecode a constraint programming language in C++
- debruijn.ecl, a model in ECLiPSe Constraint Logic Programming language
- debruijn_binary.py using Google or-tools Python interface
- DeBruijn.java using Google or-tools Java interface
- debruijn.cs using Google or-tools C# interface
- debruijn.pl, a model in SICStus Constraint Logic Programming language
- debruijn.eprime, a model in Tailor/Essence' Constraint Programming system
- DeBruijn.scala, a model in OscaR Constraint Programming system (based on Scala)
- Related: 2D de Bruijn torus/matrices in MiniZinc:
- debruijn2d.mzn: 2D de Bruijn torus/arrays/matrices
- debruijn2d_2.mzn: 2D de Bruijn torus/arrays/matrices, improved version
- debruijn2d_3.mzn: 2D de Bruijn torus/arrays/matrices, can handle non-square matrices and sub-matrices

Created by Hakan Kjellerstrand hakank@gmail.com