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}:

A de Bruijn sequence of order 3:

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

Generate a de Bruijn sequence on a string:

Applications  (1)

Generate a "prefer-one" de Bruijn sequence given the first lexicographic binary de Bruijn sequence:

Properties & Relations  (8)

A de Bruijn sequence of order 1 on a list is the list itself:

DeBruijnSequence keeps duplicate elements in the list:

The ordering of the input list determines the ordering of the de Bruijn sequence:

For an ordered list, the first de Bruijn sequence in lexicographic order is returned:

DeBruijnSequence[k,n] returns a list of length :

The subsequences of length n in DeBruijnSequence[k,n] form all possible n-tuples on the elements 0,,k-1:

Construct a binary de Bruijn sequence of order 4:

Construct all contiguous subsequences of length 4 with offset 1, and cycling through the end:

These subsequences can be obtained from an Eulerian cycle of a {k,n-1} de Bruijn graph:

For a given edge of the cycle, a subsequence is obtained by joining the digits of the name of the starting vertex to the last digit of the name of the ending vertex:

Construct a binary de Bruijn sequence of order 3:

Construct all contiguous subsequences of length 3 with offset 1, and cycling through the end:

These subsequences can be obtained from a Hamiltonian cycle of a {k,n} de Bruijn graph:

For a given edge of the cycle, a subsequence is obtained from the digits of the name of the starting vertex:

Use ShiftRegisterSequence to generate a binary de Bruijn sequence:

Check that the subsequences of length n form all possible n-tuples on the elements and :

Introduced in 2018
 (11.3)