Comment calculer des séquences de Bruijn pour des alphabets sans puissance de deux dimensions?

Question

J'essaie de calculer de Bruijn sequences pour les alphabets qui ont un certain nombre de caractères qui est pas une puissance de deux.

Pour les alphabets de 2 k caractères, le calcul des séquences de Bruijn est simple: il existe plusieurs règles simples, telles que "Prefer Ones" and "Prefer Opposites", qui permettent de générer B (2, n). B (2^k, n) est exactement le même que B (2, kn), si vous lisez les 1 et les 0 comme codes binaires pour les caractères réels de votre alphabet. Par exemple, vous pouvez interpréter B (2,8n) comme étant sur des séquences de longueur n octets.

Préférez Les on est assez simples: Ecrire n zéros. Ensuite, écrivez toujours un à moins que cela ne provoque la répétition d'une chaîne de longueur n; sinon, écris un zéro.

Actuellement, je ne vois pas comment généraliser de telles règles aux alphabets non-puissance-de-deux-taille.

Il existe une méthode générale de calcul des séquences de Bruijn via des graphes: que chaque séquence de longueur n générée par votre alphabet soit un noeud; mettre un bord de A à B ssi les n-1 caractères les plus à droite de A sont les mêmes que les n-1 caractères les plus à gauche de B. Étiqueter chaque bord avec le dernier caractère de la chaîne dans le sommet de la tête. Tout Eulerian path à travers ce graphique va générer une séquence de Bruijn, et la construction particulière que nous avons utilisée garantit qu'il y aura au moins un tel chemin. Nous pouvons utiliser Fleury's Algorithm pour construire (de manière non déterministe) un chemin eulérien:

1. Choisissez un sommet.
2. Quitte ce sommet via un bord et supprime ce bord, en choisissant uniquement les arêtes dont la suppression déconnecterait le sommet du graphe s'il n'y a pas d'alternative.
3. Ajoutez à votre chaîne l'étiquette du bord que vous venez de supprimer.
4. Aller à 2 jusqu'à ce que tous les bords soient partis.

La chaîne résultante sera une séquence de Bruijn.

Cet algorithme est un peu plus complexe à implémenter que Prefer Ones. La simplicité de Prefer Ones est qu'il suffit de consulter la sortie déjà générée pour déterminer ce qu'il faut faire. Existe-t-il un moyen simple de généraliser les préférences (ou, éventuellement, les opposés) à des alphabets de tailles non puissantes?

Answer 1

Ceci est mon implémentation C++ de l'algorithme de la figure 1 de 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; 

La référence complète du papier est: Joe Sawada et Frank Ruskey, « Un algorithme efficace pour générer Colliers à densité fixe ", SIAM Journal of Computing : 671-684, 1999.

Answer 2

Selon this web page au groupe combinatoire du département CS à l'Université de Victoria, il y a un résultat dû à Frederiksen que vous pouvez générer un de séquence Bruijn (en fait, le lexicographique plus petit) en enchaînant « la séquence lexicographique de Lyndon words de longueurs divisibles par n ". Il y a même du code source pour construire la séquence que vous pouvez demander.

Answer 3

Etes-vous uniquement intéressé par une généralisation des préférences ou voulez-vous simplement un algorithme pas si complexe? Si ce dernier est vrai alors peut-être la mise en œuvre récursive de Frank Ruskey pourrait être utile.

Il ya un an I translated that one à 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 

Uckelman remarqué que la variable alike ne fait rien. Ce qui suit produit la même séquence.

@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

L'algorithme de Duval fait la même chose itérativement (I n Python cette fois):

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)) 

Answer 5

ou vous pouvez utiliser:

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)