生成de Bruijn序列的降级算法

Algorithms for Generating de Bruijn Sequences by Reducing a Stage

讨论一种由n级de Bruijn序列产生n-1级de Bruijn序列的降级算法.方法是由n级de Bruijn序列找出其n级查寻表标签;接着通过删除该查寻表标签的相应节点的首符号,验证n-2级节点链的合法性,发现并删除节点链中的套结,实现查寻表标签的降级,最终成为n-1级查寻表标签;在此基础上建立其相应的n-1级查寻表,从而求得n-1级de Bruijn序列.文章最后给出关于算法的注解.

An algorithm for generating de Bruijn sequences by reducing a stage is discussed. The method is finding the n-1 stage Look-up table labels of n-1 stage de Bruijn sequences from an n stage de Bruijn sequence; obtaining the n-1 stage Look-up table labels by deleting the first symbol of corresponding nodes, verifying the validity of the n-2 stage node chain, finding and deleting knots on the node chains; then constructing the relative n-1 stage Look-up table and computing n-1 stage de Bruijn sequences with this Look-up table. Finally, some comments are given.