Как вычислить последовательности де Брюина для алфавитов без степеней двух размеров?

Question

Я пытаюсь вычислить последовательности де Брейна для алфавитов, количество символов которых не степень двойки.

Для алфавитов с 2 ^ k символами вычисление последовательностей де Брюина легко: есть несколько простых правил, таких как «Предпочитать» и «Предпочитать противоположности» , которые работают для генерации B (2, п). B (2 ^ k, n) точно так же, как B (2, kn), если вы читаете 1 и 0 как двоичные коды для реальных символов в вашем алфавите. Например, вы можете интерпретировать B (2,8n) как последовательности байтов длиной n.

Предпочитать единицы довольно просто: напишите нули. Затем всегда пишите единицу, если это не приведет к повторению строки n-длины; в противном случае напишите ноль.

В настоящее время я не понимаю, как обобщить такие правила в алфавитах без степени двух размеров.

Существует общий метод вычисления последовательностей де Брюина с помощью графиков: пусть каждая последовательность n-длины, сгенерированная вашим алфавитом, будет узлом; поместите ребро от A до B, если самые правые n-1 символов A совпадают с крайними левыми n-1 символами B. Пометьте каждое ребро последним символом строки в вершине головы. Любой путь Эйлера через этот граф будет генерировать последовательность де Брейна, и используемая нами особая конструкция гарантирует, что будет хотя бы один такой путь. Мы можем использовать Алгоритм Флери для (недетерминированного) построения эйлерова траектории:

1. Выберите вершину.
2. Оставьте эту вершину через какое-то ребро и удалите это ребро, выбирая только ребра, удаление которых могло бы отключить вершину от графа, если альтернативы нет.
3. Добавьте к вашей строке метку края, который вы только что удалили.
4. Переходите к 2, пока не исчезнут все края.

Полученная строка будет последовательностью де Брюина.

Этот алгоритм несколько сложнее для реализации, чем Prefer Ones. Простота Prefer One состоит в том, что нужно только просмотреть уже сгенерированный результат, чтобы определить, что делать. Существует ли простой способ обобщения предпочтительных (или, возможно, предпочтительных противоположностей) в алфавиты размером не степени двух?

Answer 1

Это моя реализация C ++ алгоритма на рисунке 1 из статьи Савады и Руски :

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;

Полная ссылка на статью: Джо Савада и Фрэнк Руски, «Эффективный алгоритм создания ожерелий с фиксированной плотностью», SIAM Journal of Computing 29 : 671-684, 1999.

Answer 2

Согласно этой веб-странице в комбинаторной группе отдела CS в UVic, благодаря Фредериксену, вы можете сгенерировать последовательность де Брейна (фактически, лексикографически наименьшую) путем объединения«лексикографическая последовательность слов Линдона длин, кратных n».Существует даже исходный код для построения последовательности, которую вы можете запросить.

Answer 3

Вас интересует только обобщение Предпочитаемых или вы просто хотите не такой сложный алгоритм?Если последнее верно, то, возможно, рекурсивная реализация Фрэнка Руски могла бы помочь.

Год назад Я перевел это на 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]=@a[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

Укельман заметил, чтопеременная 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]=@a[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

Answer 4

или вы можете использовать:

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)

Answer 5

Алгоритм Дювала делает то же самое итеративно (на этот раз в 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))