Lexicographic compositions and deBruijn sequences |
| |
Authors: | Harold Fredricksen Irving Kessler |
| |
Institution: | IDA, Communications Research Division, Thanet Road, Princeton, New Jersey 08540, USA |
| |
Abstract: | In this paper we give an algorithm to generate a new deBruijn sequence. The amount of storage required is only linear in n, the span of the sequence. We make use of the lexicographic compositions of a positive integer which we relate to binary necklaces of beads in two colors. We give a fast algorithm for generating the necklaces. Finally we relate the deBruijn sequence we generate to another sequence. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|