Author: Gerd Isenberg
Date: 04:00:43 06/24/04
Go up one level in this thread
>Hi Gerd,
>do you frequently go to outer space for some maths courses ;) ?
Unfortunately not ;-)
The deeper i try to understand that de Bruijn stuff, the more i'm aware of my
limitations of mathematical understanding ;-(
I had only some beginner courses in abstact algebra, so for instance i have
serious problems to understand Robin Chapman's or Jakob Jonsson's statements
below.
Anyway i'm able to map some move bitboards (eg. 2**from - 2**to) to an
appropriate index range without any further bitscans.
The xor-parity idea is from:
F.s. Annexstein
Generating De Bruijn Sequences: An Efficient Implementation
http://csdl.computer.org/comp/trans/tc/1997/02/t0198abs.htm
Another interesting paper on that topic:
http://www.dim.uchile.cl/~emoreno/publicaciones/LyndonSFT-WORDS03.pdf
Gerd
----------------------------------------------------------------------------
http://groups.google.com/groups?hl=en&lr=&ie=UTF8&oe=UTF8&threadm=875262742.22893%40dejanews.com&rnum=1&prev=/groups%3Fq%3Dde%2Bbruijn%2Bsequence%26hl%3Den%26lr%3D%26ie%3DUTF8%26oe%3DUTF8%26selm%3D875262742.22893%2540dejanews.com%26rnum%3D1
> I need binary de Bruijn sequences of length 2^n for n=6,...,10,
> just one sequence for each n-value. The only restriction is
> that the leftmost n+1 bits of each sequence not be all zeros.
> Unfortunately, I don't have Combinatorica, the discrete
> math software for generating them.
>
> Does anyone have that software handy to generate these?
> I think the exact function call is DeBruijnSequence[a,n] where,
> in my case, a={0,1}, n=6,...10.
>
Surely a De Bruijn sequence of length 2^n can't contain an n+1 bit
sequence of zeros. Anyway a DB sequence can be generated by a linear
recurrence. Let a_1 = a_2 = ... = a_n = 0, a_(n+1) = 1 and for r>=n+2
set a_r = c_{n-1} a_{r-1}+ ... + c_1 a_{r-n+1} + a_{r-n} (mod 2)
where X^n + c_{n-1} X^{n-1} + ... + c_1 X + 1 is an irreducible
polynomial over F_2 having the property that its roots have multiplcative
order 2^n - 1. One can obtain these by factoring the (2^n - 1)-th
cyclotomic polynomial modulo 2. Some examples:
X^6 + X + 1,
X^7 + X + 1,
X^8 + X^7 + X^2 + X + 1,
X^9 + X^4 + 1,
X^10 + X^4 + X^3 + X + 1.
Robin Chapman
Department of Mathematics
University of Exeter, EX4 4QE, UK
---------------------------------------------------------------------------
http://groups.google.com/groups?q=de+bruijn+sequence&hl=en&lr=&ie=UTF8&oe=UTF8&selm=jacob-0812952034170001%40eriks.matematik.su.se&rnum=4
The sequences mentioned are called de Bruijn sequences after the Dutch
mathematician N.G. de Bruijn, who solved the problem about the number of
such sequences. Namely, for integers m,n, the number of sequences of
length m^n such that each word of length n appears exactly once is equal
to
m^(n-1)
(m!) .
Here, we treat rotations of the same sequence as different (otherwise, we
have to divide the number by m^n). There are several proofs, all using
graph theory.
One can define a digraph D(m,n) with the words of length (n-1) as its
vertices and an arc from (a(1), ..., a(n-1)) to (a(2), ... , a(n)) for
every set {a(1), ... , a(n)} of numbers between 1 and m. This digraph is
called the de Bruijn (-Good) digraph. The problem may now be restated as
follows:
How many Eulerian tours (that is, cycles in the digraph using all arcs
exactly once) are there in the digraph D(m,n)?
(To prove that there _are_ Eulerian tours, one just have to prove that the
digraph is Eulerian, i.e., that it is connected and that the number of
arcs ending in a vertex always equals the number of arcs starting in the
same vertex. The first condition is proved by constructing a path between
every pair of vertices in the digraph. Namely, if the vertices are a =
(a(1), ... , a(n-1)) and b = (a(n), ... , a(2n-2)), then the sequence
(a(1), ... , a(2n-2)) corresponds to a path in the digraph such that the
first vertex is a and the last vertex is b. The second condition is
trivially true by definition. See below for further information.)
This problem can be solved by the aid of the Tutte Matrix Tree Theorem and the
BEST Theorem. Namely, for any digraph D, let M(D) be a matrix with a row
and a column for every vertex in D and let m(ij), the element on position
(i,j) in M(D), be equal to
\delta_{i,j} * x(i) - a(i,j)
where x(i) is the number of arcs ending in the vertex v_i corresponding to
the i'th row and a(i,j) is the number of arcs from v_i to v_j.
TUTTE MATRIX TREE THEOREM. The number of spanning directed trees in D with
root vertex v_i is equal to the determinant of the matrix obtained from
M(D) by removing the i'th row and column.
BEST THEOREM. Put T(D,i) = the number of directed spanning trees with root
v_i in D, E(D) = the number of Eulerian tours in D, d(v) = the number of
arcs ending in v = the number of arcs starting in v (the last equality is
a necessary condition for the following to hold if T(D,i)>0). Then
_____
E(D) = T(D,i) . | | (d(v)-1)!
v
(the choice of i is hence immaterial).
Those results are discussed in e.g. William T. Tutte, Graph Theory,
Addison-Wesley Publishing Company (1984); the results themselves are
rather old and published in journals not easily available. For example,
The BEST Theorem is proved in Simon Stevin 28 (1951), 203-217 (Circuits
and Trees in Oriented Linear Graphs by de Bruijn and T. van
Aardenne-Ehrenfest). In Journal of Combinatorial Theory (1967), Donald E.
Knuth showed how to prove the result by induction over n. Note that the
determinant in the Tutte matrix tree theorem is not at all trivial to
compute; in fact, one must use either an induction argument (see Knuth
above) or some transformation matrix to simplify the computations.
There are other ways of proving the result in the case where m=2. E.g.,
one may map the Eulerian tours in D(2,n) onto the Eulerian tours in
D(2,n-1) in such way that each tour in D(2,n-1) corresponds to the same
number of tours in D(2,n).
Construction of an Eulerian tour in any Eulerian digraph is not difficult
though cumbersome; consider any constructive proof of the existence of
Eulerian tours in Eulerian graphs in any elementary graph theory book.
Constructing a de Bruijn sequence without using any digraph is rather
difficult; there are no _straightforward_ algorithms or nice formulas
generating those sequences. There is something called a Feedback Shift
Register (FSR). By the aid of an FSR with the right settings, one may
generate de Bruijn sequences (or rather sequences of length one less than
the length of the de Bruijn sequences; the (0...0)-word is often missing
in applications). However, to find those settings, one has to work just as
hard as if one wants to find a sequence by hand.
What is an FSR? Considering m=2, it is a Boolean function f : B^n -> B, where
B = {0,1}. By the aid of f and an n-word (a(1), ... , a(n)) we may
construct a sequence by putting a(n+1) = f(a(1), ... , a(n)), a(n+k) =
f(a(k), ... , a(n+k-1)). E.g., if f(x,y,z) = x+z, then f(0,0,1) = 1,
f(0,1,1) = 1, f(1,1,1) = 0, f(1,1,0) = 1, f(1,0,1) = 0, f(0,1,0) = 0,
f(1,0,0) = 1, so we obtain the sequence
0011101
which will be repeated infinitely often. FSR's are often used in
cryptology to construct seemingly random sequences. However, they are less
"random" than they seem to be. When f is linear, one may use a very
elegant algorithm (Massey algorithm) to reconstruct the generating
function f if one is given a sufficiently long part of the generated
sequence (this part does not have to be so long, in general much much
shorter than the period of the sequence).
There is a book, Shift Register Sequences written by S.Goloumb (1967),
with further information about FSR's.
/Jakob Jonsson
--------------------------------------------------------------------------------
>Simply impressed as usual,
>Matthias.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.