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

2010-10-24 algorithm string math

我正在尝试计算具有多个字符( 不是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算法 (不确定)构造一条欧拉路径:

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

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

该算法的实现比“首选算法”要复杂得多。 Prefer Ones的简单性在于,只需参考已生成的输出来确定要做什么。有没有一种简单的方法可以将“首选”(或可能是“首选相反”)泛化为非2的幂的大小的字母?

Answers

根据UVic CS部门组合小组的此网页 ,由于Fredericksen的结果,您可以通过将“长度为Lynd的单词的词典序列”连接起来,生成de Bruijn序列(实际上是词典上最小的序列)可被n整除。甚至还有源代码来构建您可以请求的序列。

您是否只对“优先选择”的一般化感兴趣,还是只想要一个不太复杂的算法?如果后者是正确的,那么也许Frank Ruskey的递归实现可能会有所帮助。

一年前, 我将那个翻译成Ruby。

# De Bruijn sequence
# Original implementation by Frank Ruskey (1994)
# translated to C by Joe Sawada
# and further translated to Ruby by Jonas Elfström (2009)

@n=4
@k=10
@a=[0]
@sequence=[]

def debruijn(t, p, alike)
  if t>@n
    if @n%p==0
      1.upto(p) {|j| @sequence<<@a[j]}
    end
  else
    @a[t][email protected][t-p]
    if @a[t]>0
      debruijn(t+1,p,alike+1)
    else
      debruijn(t+1,p,alike)
    end
    (@a[t-p]+1).upto(@k-1) {|j|
      @a[t]=j
      debruijn(t+1,t,alike+1)
    }
  end
end

debruijn(1,1,0)
print @sequence.join

Uckelman注意到, alike变量没有任何作用。以下产生相同的序列。

@n=4
@k=10
@a=[0]
@sequence=[]

def debruijn(t, p)
  if t>@n
    if @n%p==0
      1.upto(p) {|j| @sequence<<@a[j]}
    end
  else
    @a[t][email protected][t-p]
    debruijn(t+1,p)
    (@a[t-p]+1).upto(@k-1) {|j|
      @a[t]=j
      debruijn(t+1,t)
    }
  end
end

debruijn(1,1)
print @sequence.join

这是我在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计算杂志29 :671-684,1999。

Duval的算法会反复执行相同的操作(这次是在Python中):

def debruijn(k, n):
    v = [0 for _ in range(n)]
    l = 1
    r = []
    while True:
        if n % l == 0:
            r.extend(v[0:l])
        for i in range(l, n):
            v[i] = v[i-l]
        l = n
        while l > 0 and v[l-1] >= k-1:
            l-=1
        if l == 0:
            break
        v[l-1] += 1
    return r

print(debruijn(3,5))

或者您可以使用:

def de_bruijn(k, n):
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

print de_bruijn(2,9)

基于@ stefan-gruenwald的代码,该代码缺少简单分类的单词集 。尽管我还没有能力进行修改,但我还是写了一些行来查找错误,这似乎是

import itertools

def debruijn (k, n) :
    v =  [ 0 for _ in range (n) ]
    l = 1
    r =  []
    while True :
        if n % l == 0 :
            r.extend (v [0:l])
        for i in range (l, n) :
            v [i] = v [i-l]
        l = n
        while l > 0 and v [l-1] >= k-1 :
            l -= 1
        if l == 0 :
            break
        v [l-1] += 1
    return r

K = int (input ( 'k ' ) )
N = int (input ( 'n ' ) )

for k in range (K) :                                # length of alphabet
    for n in range (N) :                            # length of word(s)
        List = debruijn (k, n)
        l = ''
        for L in List :
            l += str (L)
        L = itertools.product (range (k), repeat = n)
        print ( 'alphabet k', k, '\tword n', n, str ('|' + l + '|') )
        for a in L :
            searchstr = ''
            for A in a :
                searchstr += str (A)
            if not searchstr in l :
                print ( searchstr, end = ' ' )
        print ()

也可以保存在文件中:

import itertools

def debruijn (k, n) :
    v =  [ 0 for _ in range (n) ]
    l = 1
    r =  []
    while True :
        if n % l == 0 :
            r.extend (v [0:l])
        for i in range (l, n) :
            v [i] = v [i-l]
        l = n
        while l > 0 and v [l-1] >= k-1 :
            l -= 1
        if l == 0 :
            break
        v [l-1] += 1
    return r

K = int (input ( 'k ' ) )
N = int (input ( 'n ' ) )

for k in range (K) :                                # length of alphabet
    for n in range (N) :                            # length of word(s)
        List = debruijn (k, n)
        l = ''
        for L in List :
            l += str (L)
        L = itertools.product (range (k), repeat = n)
        with open (str (k) + '-' + str (n), 'w') as f :
            f.write ( 'alphabet length ' + str (k) + '\tword length ' + str (n) + '\n' + l + '\nnot in:\n' )
            for a in L :
                searchstr = ''
                for A in a :
                    searchstr += str (A)
                if not searchstr in l :
                    f.write ( searchstr + ' ' )

Related