De Bruijn Sequence and Universal Cycle Constructions

Applications

DB sequences appeared as early as 400-200 BCE in Sanskrit prosody as a mnemonic aid in remembering all possible rhythms. In particular, the DB sequence (with wraparound) 01110100(01) was represented by the word yamátárájabhánasalagám where an accented vowel represents a 1 and an unaccented vowel represents a 0.

Video games

The classic Atari game Pitfall applied an 8-stage linear feedback shift register (LFSR) to generate 255 different map locations that Harry could travel in the jungle. Each 8-bit binary string (missing the all 0 string) represented a unique location that included snakes, scorpions, alligators and different types of treasures.

   

A nice discussion is provided in this blog post and this ASCII version of the game. For more, see Retrogame Archeology.

Card tricks

The following trick has been performed by renowned mathematicians Persi Diaconis and Ron Graham and is detailed in their book Magical Mathematics.

The cards: Consider a reduced deck of playing cards with only values Ace through 8. Each card can be assigned a unique bitstring of length $n=5$ as follows: The first two bits encode the suit (00 = ♣, 01 = ♠, 10 = , and 11 = ) and the last three bits encode the value (000 = A, 001 = 2, ..., 111 = 8). Note the first bit provides the color of the card (0=black, 1=red).

00000 = A ♣     01000 = A ♠     10000 = A     11000 = A
00001 = 2 ♣ 01001 = 2 ♠ 10001 = 2 11001 = 2
00010 = 3 ♣ 01010 = 3 ♠ 10010 = 3 11010 = 3
00011 = 4 ♣ 01011 = 4 ♠ 10011 = 4 11011 = 4
00100 = 5 ♣ 01100 = 5 ♠ 10100 = 5 11100 = 5
00101 = 6 ♣ 01101 = 6 ♠ 10101 = 6 11101 = 6
00110 = 7 ♣ 01110 = 7 ♠ 10110 = 7 11110 = 7
00111 = 8 ♣ 01111 = 8 ♠ 10111 = 8 11111 = 8

The setup: Order the cards based on your favorite DB-successor. Often the trick is described by applying a LFSR, but the DB-successor PCR4 is very easy to apply if you can distinguish necklaces quickly. Using PCR4, we get the (cyclic) DB sequence 00000111110111001100010110101001. Thus the cards are ordered:

A ♣, 2 ♣, 4 ♣, 8 ♣, 8 ♠, 8 , 7 , 6 , 4 , 8 , 7 ♠, 5 , 2 , 4 , 7 ♣, 5 ♠,
A , 2 , 3 ♣, 6 ♣, 4 ♠, 7 , 6 ♠, 3 , 6 , 3 ♠, 5 , 2 ♠, 3 , 5 ♣, A ♠, A .

The performance: Flash the audience the seemingly random sequence of cards. Then ask an audience member to cut the cards. Cut them again. Cut them again. (This does not affect the cyclic nature of the sequence!). Now lay out the first 5 cards in order, face down. The key information required is the color of each card. Ask an audience member to look at the cards and report which ones are black=0. Also ask them several other unrelated questions for showmanship: What did you have for breakfast? Suppose, as an example, the cards are (red, black, red, red, black) = 10110. Thus, we already know the first card is 7 . Now applying the simple successor rule PCR4 used to create the DB sequence we can predict the color of the next 4 cards. A minor achievement leading up to the big reveal. Recommendation: use blank paper and pretend to record audience answers, when in fact you are calculating the colors. From our example, they will be 1010 = red, black, red, black. Using this information, we know the bit sequence from these 9 cards to be 101101010. Now amaze the audience by revealing the original 5 cards to be: 7 , 6 ♠, 3 , 6 , 3 ♠.

Cipher locks

A classic cipher lock application is from Fredricksen's survey [Fre82]:

   

Of course, the sequence required in this application is a DB sequence including the wraparound. For an interesting read on cracking such passwords see this blog post.

Cryptography and pseudo-random number generation

Genomic assembly

Robotics and perfect maps

References

  • [Fre82] H. Fredricksen. A survey of full length nonlinear shift register cycle algorithms. Siam Review, 24(2):195-221, 1982.