De Bruijn Sequence
Home * Programming * Data * De Bruijn Sequence
In combinatorial mathematics, a k-ary De Bruijn Sequence B(k, n) of order n, named after the Dutch mathematician Nicolaas de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once [1]. In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in hashing sets like Piece-Sets or Square-sets, also called Bitboards, most notably in Bit scanning [2] .
Binary alphabet
According to De Bruijn himself [3] , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest [4] and himself.
Binary digits or bits inside a computer word are B(2, n) de Bruijn sequences, with 2n bits length and equal number of ones and zeros, with 2n overlapping unique n-bit subsequences. Since the sequences are cyclic and n-1 subsequences need to wrap, we restrict them to at least n-1 leading zeros, to make them overlap the hidden trailing “zeros”.
Odd sequences have n leading zeros. The even ones with n-1 leading zeros are rotated (shifted) left by one. Due to n leading zeros of these odd sequences we further consider, the first subsequence[0] is zero. Due to the overlapping, each subsequence[i+1] is dependent from subsequence[i]. The doubled value incremented by either zero or one. Since subsequence[0] is zero, a second zero subsequence with six consecutive binary zeros is further prohibited, and subsequence[1] must be one. Subsequence index i is counted from most significant bit left to right, and therefor reversed from usual bit-index. A modulo 2n restricts all subsequences to n bits:
The Cardinality of all distinct B(2, n) de Bruijn sequences is:
| n | 2n-1 - n | B(2, n)|
1 | ||
0 | ||
1 | ||
2 | ||
0 | ||
1 | ||
3 | ||
1 | ||
2 | ||
4 | ||
4 | ||
16 | ||
5 | ||
11 | ||
2,048 | ||
6 | ||
26 | ||
67,108,864 | ||
7 | ||
57 | ||
144,115,188,075,855,872 | ||
8 | ||
120 | ||
~1.329e+36 | ||
B(2, 1)
B(2, 2)
B(2, 2) implies 22 or 4-bit sequences. There is one odd four-bit de Bruijn sequence with four overlapping unique two-bit subsequences, 0x3.
B(2, 3)
B(2, 3) implies 23 or 8-bit sequences. There are two odd eight-bit sequences with eight overlapping unique three-bit subsequences, 0x17 and 0x1d. Note that the five relevant bits are reversed.
B(2, 4)
B(2, 4) implies 24 or 16 bit sequences. There are 16 odd 16-bit sequences with 16 overlapping unique four-bit subsequences:
for instance 0x0d2f:
B(2, 5)
B(2, 5) implies 25 or 32 bit sequences. There are 2^11 or 2,048 odd 32-bit sequences with 32 overlapping unique five-bit subsequences, for instance 0x076be629
B(2, 6)
B(2, 6) implies 26 or 64 bit sequences. There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit subsequences, for instance 0x022fdd63cc95386d
De Bruijn Graphs
A De Bruijn graph is a directed graph representing overlaps between sequences of symbols [5] .
- Each vertex has exactly m incoming and m outgoing edges
- Each n-dimensional de Bruijn graph is the line digraph of the (n-1)-dimensional de Bruijn graph
- Each de Bruijn graph is Eulerian and Hamiltonian. The Euler cycles and Hamiltonian cycles of these graphs are de Bruijn sequences.
[ The graph construction of the three smallest binary de Bruijn graphs
B(2, 4) Graph
[ A De Bruijn graph. Every four-digit sequence occurs exactly once if one traverses every edge exactly once and returns to one’s starting point.
De Bruijn Graph on a Chess Board
A directed De Bruijn Graph of B(2, 6) sequences with Little-Endian Rank-File Mapping board coordinates (a1 = 0, b1 = 1, h8 = 63). For topology reasons, almost each node (except a1 and h8) of the graph is deconcentrated and appears twice in the form of two reversed binary trees. The leaf outputs join the respective reversed tree. Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares exactly once.
De Bruijn Networks
So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by Feldmann et al. to connect Transputer networks [6] [7] .
See also
- Nicolaas de Bruijn
- De Bruijn Multiplication from BitScan
- De Bruijn Sequence Generator
- Prouhet–Thue–Morse Sequence
- Pseudorandom Number Generator
Selected Publications
1894
- Camille Flye Sainte-Marie (1894). Solution to question nr. 48, L’Intermédiaire des Mathématiciens 1, reproduced in Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf
1946
- Nicolaas de Bruijn (1946). A Combinatorial Problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764.
- Jack Good (1946). Normal Recurring Decimals. Journal of the London Mathematical Society [8]
1950 …
- Lester Randolph Ford, Jr. (1957). A Cyclic Arrangement of M-Tuples. Report No. P-1071. Rand Corporation
- Solomon W. Golomb (1967, 1982). Shift Register Sequences. Holden-Day Inc., revised 2nd edition, Aegean Park Press
- Harold M. Fredricksen (1968). Disjoint Cycles from the de Bruijn Graph. Ph.D. thesis, University of Southern California, advisor Solomon Wolf Golomb
1970 …
- Harold M. Fredricksen (1970). The lexicographically least de Bruijn cycle. Journal of Combinatorial Theory, Vol. 9, No. 1
- Abraham Lempel (1970). On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers. IEEE Transactions on Computers, Vol. 19, No. 12
- Harold M. Fredricksen (1972). Generation of the Ford Sequence of Length 2n, n Large. JPL Technical Report 32-1526, Vol. IV, pdf
1990 …
- Yuejiang Huang (1990). A new algorithm for the generation of binary de Bruijn sequences. Journal of Algorithms, Vol. 11, No. 1
- Chris J. Mitchell, Tuvi Etzion, Kenneth G. Paterson (1996). A method for constructing decodable de Bruijn Sequences. pdf via CiteSeerX
- Fred S. Annexstein (1997). Generating De Bruijn Sequences: An Efficient Implementation. IEEE Transactions on Computers, Vol. 46, No. 2, pdf, Supplement: C-code implementation
- Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf
2000 …
- Vladimir Raphael Rosenfeld (2002). Enumerating De Bruijn Sequences. Institute of Evolution, University of Haifa, pdf
- Vladimir Raphael Rosenfeld (2002). Enumerating Kautz Sequences. Institute of Evolution, University of Haifa, pdf
- Anwitaman Datta, Sarunas Girdzijauskas, Karl Aberer (2004). On de Bruijn routing in distributed hash tables: There and back again. P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, pdf
- Pierre Fraigniaud, Philippe Gauron (2005). D2B: a de Bruijn Based Content-Addressable Network. pdf
- Drew Armstrong (2006). De Bruijn Sequences. pdf
- Jean Berstel, Dominique Perrin (2007). The origins of combinatorics on words. European Journal of Combinatorics 28, pdf
2010 …
- Yaw-Ling Lin, Charles B. Ward, Bharat Jain, Steven Skiena (2011). Constructing Orthogonal de Bruijn Sequences. LNCS 6844, WADS 2011
- Zuling Chang, Martianus Frederic Ezerman, San Ling, Huaxiong Wang (2016). On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials. arXiv:1611.10088 [9]
- Zuling Chang, Martianus Frederic Ezerman, Adamas Aqsa Fahreza, San Ling, Huaxiong Wang (2017). Large Order Binary de Bruijn Sequences via Zech’s Logarithms. arXiv:1705.03150 [10]
- Joe Sawada, Aaron Williams (2017). Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences. Journal of Discrete Algorithms, Vol. 43, No. C, pdf
External Links
- De Bruijn sequence from Wikipedia
- De Bruijn graph from Wikipedia
- Kautz graph from Wikipedia
- Koorde from Wikipedia
- A166315 - OEIS
- Lyndon word from Wikipedia
- If - Forgotten Roads, Beat-Club #71, September 25, 1971, YouTube Video
References
- ↑ De Bruijn sequence from Wikipedia
- ↑ Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word. pdf
- ↑ Nicolaas de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, pdf
- ↑ Nicolaas de Bruijn (1985). In Memoriam T. van Ardenne-Ehrenfest. pdf
- ↑ De Bruijn graph from Wikipedia
- ↑ Rainer Feldmann, Peter Mysliwietz, Burkhard Monien (1991). A Fully Distributed Chess Program. Advances in Computer Chess 6, pdf
- ↑ Rainer Feldmann (1993). Game Tree Search on Massively Parallel Systems Phd-Thesis, pdf
- ↑ Recurring decimal from Wikipedia
- ↑ LFSR from Wikipedia
- ↑ Zech’s logarithm from Wikipedia