algorithm - 如何计算非二次幂字母表的 de Bruijn 序列？

Question

我正在尝试计算 de Bruijn sequences对于具有多个不是二的幂的字符的字母表。

对于具有 2^k 个字符的字母表，计算 de Bruijn 序列很容易:有几个简单的规则，例如 "Prefer Ones" and "Prefer Opposites"用于生成 B(2,n)。 B(2^k,n) 与 B(2,kn) 完全相同，如果您将 1 和 0 读作字母表中实际字符的二进制代码。例如，您可以将 B(2,8n) 解释为长度超过 n 的字节序列。

Prefer Ones 非常简单:写入 n 个零。然后，总是写一个，除非它会导致重复一个 n 长的字符串；否则，写一个零。

目前，我不知道如何将此类规则推广到非二次方大小的字母表。

通过图计算de Bruijn序列有一个通用的方法:让你的字母表生成的每一个n长度的序列都是一个节点；当且仅当 A 最右边的 n-1 个字符与 B 最左边的 n-1 个字符相同时，从 A 到 B 放置一条边。用头顶点中字符串的最后一个字符标记每条边。任何Eulerian path通过这个图将生成一个 de Bruijn 序列，我们使用的特殊结构保证至少会有一个这样的路径。我们可以使用 Fleury's Algorithm (非确定性地)构建欧拉路径:

1. 选择一个顶点。
2. 通过某条边离开该顶点并删除该边，如果别无选择，则只选择删除这些边会使该顶点与图形断开连接的边。
3. 将您刚刚删除的边的标签附加到您的字符串。
4. 转到 2，直到所有边都消失。

生成的字符串将是 de Bruijn 序列。

这个算法比 Prefer Ones 更复杂一些。 Prefer Ones 的简单之处在于，只需引用已经生成的输出即可确定要做什么。有没有一种直接的方法可以将 Prefer Ones(或者，Prefer Opposites)推广到非二次幂大小的字母表？

Answer 1

这是我对图 1 中算法的 C++ 实现，来自 a paper by Sawada and Ruskey :

void debruijn(unsigned int t,
              unsigned int p,
              const unsigned int k,
              const unsigned int n,
              unsigned int* a,
              boost::function<void (unsigned int*,unsigned int*)> callback)
{
  if (t > n) {
    // we want only necklaces, not pre-necklaces or Lyndon words
    if (n % p == 0) {
      callback(a+1, a+p+1);
    }
  }
  else {
    a[t] = a[t-p];

    debruijn(t+1, p, k, n, a, callback);

    for (unsigned int j = a[t-p]+1; j < k; ++j) {
      a[t] = j;
      debruijn(t+1, t, k, n, a, callback);
    }
  }
}

struct seq_printer {
  const std::vector<char>& _alpha;

  seq_printer(const std::vector<char>& alpha) : _alpha(alpha) {}

  void operator() (unsigned int* a, unsigned int* a_end) const {
    for (unsigned int* i = a; i < a_end; ++i) {
      std::cout << _alpha[*i];
    }
  }
};

...

std::vector<char> alpha;
alpha.push_back('a');
alpha.push_back('b');
alpha.push_back('c');

unsigned int* a = new unsigned int[N+1];
a[0] = 0;

debruijn(1, 1, alpha.size(), N, a, seq_printer(alpha));
if (N > 1) std::cout << alpha[0];
std::cout << std::endl;

delete[] a;

该论文的完整引用文献是:Joe Sawada 和 Frank Ruskey，“一种生成固定密度项链的有效算法”，SIAM 计算杂志 29:671-684，1999。