如何计算德Bruijn序列的非电源-2大小的字母？ [英] How to compute de Bruijn sequences for non-power-of-two-sized alphabets?

问题描述

我试图来计算德布鲁因序列获取其中有一个字符数是不字母表的二的幂。

I'm trying to compute de Bruijn sequences for alphabets which have a number of characters which is not a power of two.

有关字母与2 ^ķ人物，计算德布鲁因序列容易是：有几个简单的规则，如的preFER一和preFER对立统一它产生乙的工作（2，N）。 B（2 ^ K，N）是完全一样B（2，KN），如果你读了1和0的二进制codeS为您字母表的实际字符。例如，你可以跨preT B（2,8n）作为字节数的正长序列。

For alphabets with a 2^k characters, calculating de Bruijn sequences is easy: There are several simple rules, such as "Prefer Ones" and "Prefer Opposites" which work for generating B(2,n). B(2^k,n) is exactly the same as B(2,kn), if you read the 1s and 0s as binary codes for the actual characters in your alphabet. E.g., you can interpret B(2,8n) as being over n-length sequences of bytes.

preFER问鼎很简单：写N个零。然后，总是写一个，除非它会导致正长串的重复;否则，写一个零。

Prefer Ones is quite simple: Write n zeros. Then, always write a one unless it would cause the repetition of an n-length string; otherwise, write a zero.

presently，我看不出如何推广这些规则对非幂的两个大字母。

Presently, I don't see how to generalize such rules to non-power-of-two-sized alphabets.

还有通过图形计算德布鲁因序列的通用方法：让你的字母产生的每一个n长序列是一个节点;把一个边缘从A到当且仅当A的最右边的n-1个字符B是相同的作为B的最左边的n-1个字符标记每个边缘与该串中的头部顶点的最后一个字符。通过该曲线图任何欧拉路径中会产生一个去Bruijn的序列，和特有的结构，我们使用的保证将有至少这样的一个路径。我们可以使用弗勒里的算法来（非确定性）构造一个一笔画问题

There's a general method for calculating de Bruijn sequences via graphs: Let each n-length sequence generated by your alphabet be a node; put an edge from A to B iff the rightmost n-1 characters of A are the same as the leftmost n-1 characters of B. Label each edge with the last character of the string in the head vertex. Any Eulerian path through this graph will generate a de Bruijn sequence, and the peculiar construction we used guarantees that there will be at least one such path. We can use Fleury's Algorithm to (nondeterministically) construct an Eulerian path:

1. 选择一个顶点。
2. 将顶点通过一些边和删除边，只能选择边缘的缺失会从图中断开顶点，如果没有其他选择。
3. 追加到您的字符串刚删除的边缘的标签。
4. 转到2，直到所有的边都没有了。

结果字符串将是一个德布鲁因序列。

The resulting string will be a de Bruijn sequence.

这个算法是较为复杂的实现比preFER的。的preFER问鼎的简单性是一个只需要协商已经产生，以确定如何输出。有没有一种简单的方法来概括preFER问鼎（或者，可能是preFER对立统一）非幂的两种尺寸的字母？

This algorithm is somewhat more complex to implement than Prefer Ones. The simplicity of Prefer Ones is that one needs only to consult the output already generated to determine what to do. Is there a straightforward way to generalize Prefer Ones (or, possibly Prefer Opposites) to alphabets of non-power-of-two sizes?

推荐答案

这是我的C ++从的一文由泽田和Ruskey ：

This is my C++ implementation of the algorithm in Figure 1 from 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;

有关的文件的完整参考是：乔泽田和弗兰克Ruskey，一种高效的算法生成项链与固定密度，计算的 29 的的SIAM杂志：671-684，1999年

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.

这篇关于如何计算德Bruijn序列的非电源-2大小的字母？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！