A Simple Combinatorial Algorithm for de Bruijn Sequences

作者:Alhakim Abbas M*
来源:AMERICAN MATHEMATICAL MONTHLY, 2010, 117(8): 728-732.
DOI:10.4169/000298910X515794

摘要

This paper presents a combinatorial method to construct a de Bruijn sequence for any order n. The method is similar to that of the well-known prefer-one algorithm. The resulting sequences are compared and both methods are shown to be special cases of a unifying graph construction that is capable of generating all de Bruijn sequences.