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

Question

我正在尝试计算de Bruijn序列的字母表,这些字母表有许多不是2的幂的字符.

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

首选Ones很简单:写n个零.然后,总是写一个,除非它会导致重复n长度的字符串; 否则,写一个零.

目前,我没有看到如何将这些规则推广到非幂级的两个字母表.

有一种通过图表计算de Bruijn序列的一般方法:让你的字母表生成的每个n长度序列成为一个节点; 如果A的最右边的n-1个字符与B的最左边的n-1个字符相同,则将A从边缘放到B边缘.用头顶点中的字符串的最后一个字符标记每个边缘.通过该图的任何欧拉路径将生成de Bruijn序列,并且我们使用的特殊构造保证将存在至少一条这样的路径.我们可以使用Fleury算法(非确定性地)构建欧拉路径:

1. 选择一个顶点.
2. 通过某个边缘保留该顶点并删除该边缘,只选择边缘,如果没有其他选择,删除将断开顶点与图形的连接.
3. 在您的字符串中附加刚刚删除的边缘的标签.
4. 转到2直到所有边缘消失.

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

该算法比Prefer Ones实现起来要复杂一些.Prefer Ones的简单之处在于,只需查阅已生成的输出即可确定要执行的操作.有没有一种简单的方法可以将Prefer Ones(或者,可能更喜欢Opposites)推广到非二次幂大小的字母表？

Answer 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;

该论文的完整参考文献是:Joe Sawada和Frank Ruskey,"用于生成具有固定密度的项链的有效算法",SIAM Journal of Computing 29:671-684,1999.