产生k元de Bruijn序列的一个递归算法

A recursive algorithm for generating k-ary de Bruijn sequences

通过合并纯轮换移位寄存器状态图中的所有圈,给出了生成k元de Bruijn序列的一个递归算法,不再采用“主圈并一个圈”的经典并圈法,而是利用了“主圈并一组共轭圈”的新方法,减少了选择桥状态的次数;同时,给出了新的选择桥状态的规则,简化了判断一个状态是否是桥状态的计算,从而加快了并圈的速度。

By joining all cycles in the state graph of pure cycling register,a recursive algorithm for generating k-ary de Bruijn sequences is given in this paper. Not the classical method that the main cycle is extended by joining to it one cycle but a new method that the main cycle is extended by joining to it a subset of cycles is used in the algorithm. The method reduces the time of choosing bridging states. On the other hand, new regulations of choosing bridging states are given in this paper. The regulations reduce the calculations of judging whether a state is a bridging state or not. The presented recursive algorithm accelerates the speed of joining cycles.