De Bruijn sequences
A De Bruijn sequence is defined as the shortest cyclic sequence that incorporates all substrings of a certain length of an alphabet.
For instance, the binary strings of length 3 are all included in the
following string:
sage: DeBruijnSequences(2,3).an_element()
[0, 0, 0, 1, 0, 1, 1, 1]
They can be obtained as a subsequence of the cyclic De Bruijn sequence of
parameters and
:
sage: seq = DeBruijnSequences(2,3).an_element()
sage: print Word(seq).string_rep()
00010111
sage: shift = lambda i: [(i+j)%2**3 for j in range(3)]
sage: for i in range(2**3):
... print (Word(map(lambda (j,b): b if j in shift(i) else '*',
... enumerate(seq))).string_rep())
000*****
*001****
**010***
***101**
****011*
*****111
0*****11
00*****1
This sequence is of length , which is best possible as it is the number of
-ary strings of length
. One can equivalently define a De Bruijn sequence
of parameters
and
as a cyclic sequence of length
in which all
substring of length
are different.
See also the Wikipedia article on De Bruijn sequences.
TESTS:
Checking the sequences generated are indeed valid:
sage: for n in range(1, 7):
... for k in range(1, 7):
... D = DeBruijnSequences(k, n)
... if not D.an_element() in D:
... print "Something's dead wrong (n=%s, k=%s)!" %(n,k)
... break
AUTHOR:
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Represents the De Bruijn sequences of given parameters and
.
A De Bruijn sequence of parameters and
is defined as the shortest
cyclic sequence that incorporates all substrings of length
a
-ary
alphabet.
This class can be used to generate the lexicographically smallest De Bruijn sequence, to count the number of existing De Bruijn sequences or to test whether a given sequence is De Bruijn.
INPUT:
EXAMPLES:
Obtaining a De Bruijn sequence:
sage: seq = DeBruijnSequences(2, 3).an_element()
sage: print seq
[0, 0, 0, 1, 0, 1, 1, 1]
Testing whether it is indeed one:
sage: seq in DeBruijnSequences(2, 3)
True
The total number for these parameters:
sage: DeBruijnSequences(2, 3).cardinality()
2
Note
This function only generates one De Bruijn sequence (the smallest lexicographically). Support for generating all possible ones may be added in the future.
TESTS:
Setting k to 1 will return 0:
sage: DeBruijnSequences(1, 3).an_element()
[0]
Setting n to 1 will return the alphabet:
sage: DeBruijnSequences(3, 1).an_element()
[0, 1, 2]
The test suite:
sage: d=DeBruijnSequences(2, 3)
sage: TestSuite(d).run()
Returns the lexicographically smallest De Bruijn sequence with the given parameters.
ALGORITHM:
The algorithm is described in the book “Combinatorial Generation” by Frank Ruskey. This program is based on a Ruby implementation by Jonas Elfström, which is based on the C program by Joe Sadawa.
EXAMPLE:
sage: DeBruijnSequences(2, 3).an_element()
[0, 0, 0, 1, 0, 1, 1, 1]
Returns the number of distinct De Bruijn sequences for the object’s parameters.
EXAMPLE:
sage: DeBruijnSequences(2, 5).cardinality()
2048
ALGORITHM:
The formula for cardinality is [1].
REFERENCES:
[1] | Rosenfeld, Vladimir Raphael, 2002: Enumerating De Bruijn Sequences. Communications in Math. and in Computer Chem. |
The generating function for De Bruijn sequences. This avoids the object creation, so is significantly faster than accessing from DeBruijnSequence. For more information, see the documentation there. The algorithm used is from Frank Ruskey’s “Combinatorial Generation”.
INPUT:
EXAMPLES:
sage: from sage.combinat.debruijn_sequence import debruijn_sequence
sage: debruijn_sequence(3, 1)
[0, 1, 2]
Given a sequence of integer elements in , tests whether it
corresponds to a De Bruijn sequence of parameters
and
.
INPUT:
EXAMPLE:
sage: from sage.combinat.debruijn_sequence import is_debruijn_sequence
sage: s = DeBruijnSequences(2, 3).an_element()
sage: is_debruijn_sequence(s, 2, 3)
True
sage: is_debruijn_sequence(s + [0], 2, 3)
False
sage: is_debruijn_sequence([1] + s[1:], 2, 3)
False