DeBruijnSequence

DeBruijnSequence[list,n]

gives a de Bruijn sequence on the elements in list taken n at a time.

DeBruijnSequence[k,n]

gives a de Bruijn sequence on the elements 0,,k-1.

DeBruijnSequence["string",n]

gives a de Bruijn sequence on the characters in "string".

Details

  • A de Bruijn sequence of order n on a list of length k is a cyclic sequence of length in which every possible block of length n taken from the list occurs exactly once as a contiguous subsequence.
  • For a list of length k and blocks of length n, there exist distinct de Bruijn sequences.

Examples

open allclose all

Basic Examples  (3)

Generate a de Bruijn sequence of order 2 on the list {0,1}:

In[1]:=
Click for copyable input
Out[1]=

A de Bruijn sequence of order 3:

In[2]:=
Click for copyable input
Out[2]=

Return a de Bruijn sequence on the elements 0,,3:

In[1]:=
Click for copyable input
Out[1]=

Generate a de Bruijn sequence on a string:

In[1]:=
Click for copyable input
Out[1]=

Applications  (1)

Properties & Relations  (8)

See Also

DeBruijnGraph  ShiftRegisterSequence  Tuples  Partition

Introduced in 2018
(11.3)