New search (restrictions: 1 < n < 15, 1 < k < 15, k^n < 50000 )
See below for more info about Bruijn sequences.
You may also want try my de Bruijn sequence Java Applet.
de Bruijn sequence, k=2, n=3
The following is a de Bruijn sequence of a k=2 sized alphabet with
string length of n=3 . Please note that the sequence is circular, i.e. it wraps "around the end", indicated by setting the first n-1 digits last in the sequence (inside parenthesis).
Sequence length: k^n = 2^3 = 8 (with the "wrap": k^n+(n-1) = 2^3+(3-1) = 10)
0 0 0 1 0 1 1 1 (0 0)
The table below shows a more structured version of the sequence:
0 0 1
0 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.
The code/algortihm for this program is from the inspirational Combinatorial
Object Server, COS, at http://theory.cs.uvic.ca/~cos/.
Back to my homepage
- 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
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:
Created by Hakan Kjellerstrand firstname.lastname@example.org