如何计算非2的幂的字母表的de Bruijn序列？

一尘不染

如何计算非2的幂的字母表的de Bruijn序列？

algorithm

我正在尝试计算具有多个字符（ 不是2 的幂）的字母的de
Bruijn序列。 __

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

首选一个很简单：写n个零。然后，总是写一个，除非会导致重复一个n长度的字符串。否则，写一个零。

目前，我看不到如何将此类规则推广到非2的幂次方的字母。

有一种通过图形计算de
Bruijn序列的通用方法：让您的字母生成的每个n长度序列为一个节点；如果A的最右边的n-1个字符与B的最左边的n-1个字符相同，则从A到B放置一个边。用头顶点中字符串的最后一个字符标记每个边。通过该图的任何欧拉路径都会生成一个de
Bruijn序列，并且我们使用的特殊构造可以保证至少会有一条这样的路径。我们可以使用Fleury算法（不确定地）构造一条欧拉路径：

选择一个顶点。
通过某个边保留该顶点并删除该边，仅在没有其他选择的情况下，选择其删除将使顶点与图形断开连接的边。
在字符串上附加刚删除的边缘的标签。
转到2，直到所有边缘消失。

结果字符串将是de Bruijn序列。

该算法的实现比“首选算法”要复杂一些。Prefer
Ones的简单性在于，只需参考已生成的输出来确定要做什么。有没有一种简单的方法可以将“优先选择的”（或者可能是“优选相反的”）归纳为非2的幂的大小的字母？

阅读 293

2020-07-28

共1个答案

一尘不染

这是我在Sawada和Ruskey的论文中对图1中算法的C
++实现：

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;

The full reference for the paper is: Joe Sawada and Frank Ruskey, “An
Efficient Algorithm for Generating Necklaces with Fixed Density”, SIAM Journal
of Computing 29 :671-684, 1999.

2020-07-28