algorithm - 如何迭代生成 de Bruijn 序列？

Question

我正在寻找一种迭代生成 de Bruijn 序列的方法，而不是使用递归。我的目标是逐个字符地生成它。

我找到了 some example code in Python用于生成 de Bruijn 序列并将其翻译成 Rust。我还不能很好地理解这项技术来创建我自己的方法。

翻译成 Rust:

fn gen(sequence: &mut Vec<usize>, a: &mut [usize], t: usize, p: usize, k: usize, n: usize) {
    if t > n {
        if n % p == 0 {
            for x in 1..(p + 1) {
                sequence.push(a[x])
            }
        }
    } else {
        a[t] = a[t - p];
        gen(sequence, a, t + 1, p, k, n);
        for x in (a[t - p] + 1)..k {
            a[t] = x;
            gen(sequence, a, t + 1, t, k, n);
        }
    }
}

fn de_bruijn<T: Clone>(alphabet: &[T], n: usize) -> Vec<T> {
    let k = alphabet.len();
    let mut a = vec![0; n + 1];
    let vecsize = k.checked_pow(n as u32).unwrap();
    let mut sequence = Vec::with_capacity(vecsize);
    gen(&mut sequence, &mut a, 1, 1, k, n);
    sequence.into_iter().map(|x| alphabet[x].clone()).collect()
}

然而，这无法迭代生成 - 它会经历一团乱七八糟的递归和迭代，不可能解开成一个单一的状态。

Answer 1

考虑这种方法:

1. 从每个项链类别中选择第一个(按字典顺序)代表

   Here is Python code用于生成包含 d 的 (binary) 项链的代表(可以对所有 d 值重复)。 Sawada article link

2. 按字典顺序对代表进行排序

3. 对每个代表进行周期性归约(如果可能):如果字符串是周期性的s = p^m，如010101，选择01

   要查找期间，可以使用 string doubling或 z-algorithm (我希望编译语言更快)

4. 串联归约

   n=3,k=2 的例子:
   排序代表:000, 001, 011, 111
   减少:0、001、011、1
   结果:00010111

Jörg Arndt 的书 "Matters Computational" 中描述了相同的基本方法(使用 C 代码) , 第 18 章

wiki 中提到了类似的方法

An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n

您可能会寻找有效的方法来生成合适的 Lyndon 词