De Bruijn Words
Presentation
De Bruijn's strings are the shortest circular chains of characters, containing all the words of length n on an alphabet A.
(These words can be, for example, of the access codes of doors of buildings... )
(These words can be, for example, of the access codes of doors of buildings... )
The alphabet A of p = |A| letters and one seeks a circular chain containing all the words of n characters written in this alphabet.
G is the digraph whose vertices are the pn-1 words of n-1 characters and whose arcs arcs are the pn words of n characters, the arc of origin aX and extremity Xb is aXb.
Find a word of de Bruijn is the same to find an eulerian circuit.
G is the digraph whose vertices are the pn-1 words of n-1 characters and whose arcs arcs are the pn words of n characters, the arc of origin aX and extremity Xb is aXb.
Find a word of de Bruijn is the same to find an eulerian circuit.
Example
The 25 words of 2 letters using the five figures from 0 to 4 included, are contained in the circular chain 0102030411213142232433440
(00 is obtained by closing again the chain on itself ...3440<->01020...)
The JavaScript program used below stops its research with the 10th chain solution. Each solution is written on a different line.
(00 is obtained by closing again the chain on itself ...3440<->01020...)
The JavaScript program used below stops its research with the 10th chain solution. Each solution is written on a different line.