k-өлшемді әріптер жиынындағы барлық ұзындығы k тізбектерді аралау

Cycle through all length k sequences

In combinatorial mathematics, a de Bruijn sequence of order n on a size k alphabet A is a cyclic sequence in which every possible length n string on A occurs exactly once as a substring (i. e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at least kn symbols. And since B(k, n) has exactly kn symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once. The number of distinct de Bruijn sequences B(k, n) is

The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn, who wrote about them in 1946. As he later wrote, the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by The generalization to larger alphabets is due to Automata for recognizing these sequences are denoted as de Bruijn automata. In most applications, A = {0,1}.

The earliest known example of a de Bruijn sequence comes from Sanskrit prosody where, since the work of Pingala, each possible three syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic yamātārājabhānasalagām is used, in which each three syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3 tuples, is of unknown antiquity, but is at least as old as Charles Philip Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by Pāṇini". In 1894, A. de Rivière raised the question in an issue of the French problem journal L'Intermédiaire des Mathématiciens, of the existence of a circular arrangement of zeroes and ones of size that contains all binary sequences of length The problem was solved (in the affirmative), along with the count of distinct solutions, by Camille Flye Sainte Marie in the same year. This was largely forgotten, and proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well known. Karl Popper independently describes these objects in his The Logic of Scientific Discovery (1934), calling them "shortest random like sequences".

Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse or negation of the other. Two of the 16 possible B(2, 4) in the same alphabet are 0000100110101111 and 0000111101100101. Two of the 2048 possible B(2, 5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.

The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1) dimensional de Bruijn graph). An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n.

An inverse Burrows–Wheeler transform can be used to generate the required Lyndon words in lexicographic order. de Bruijn sequences can also be constructed using shift registers or via finite fields.

de Bruijn cycles are of general use in neuroscience and psychology experiments that examine the effect of stimulus order upon neural systems, and can be specially crafted for use with functional magnetic resonance imaging.

The symbols of a de Bruijn sequence written around a circular object (such as a wheel of a robot) can be used to identify its angle by examining the n consecutive symbols facing a fixed point. This angle encoding problem is known as the "rotating drum problem". Gray codes can be used as similar rotary positional encoding mechanisms, a method commonly found in rotary encoders.

An f fold n ary de Bruijn sequence is an extension of the notion n ary de Bruijn sequence, such that the sequence of the length contains every possible subsequence of the length n exactly f times. For example, for the cyclic sequences 11100010 and 11101000 are two fold binary de Bruijn sequences. The number of two fold de Bruijn sequences, for is , the other known numbers are , , and .

A de Bruijn torus is a toroidal array with the property that every k ary m by n matrix occurs exactly once. Such a pattern can be used for two dimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the m by n matrix directly adjacent to the sensor, and calculating its position on the de Bruijn torus.

Computing the position of a particular unique tuple or matrix in a de Bruijn sequence or torus is known as the de Bruijn decoding problem. Efficient \color{Blue} O(n \log n) decoding algorithms exist for special, recursively constructed sequences and extend to the two dimensional case. de Bruijn decoding is of interest, e. g., in cases where large sequences or tori are used for positional encoding.