Wie berechnet man de Bruijn-Sequenzen für Alphabete, die nicht die Potenz von zwei haben?

Question

Ich versuche zu berechnen de Bruijn-Sequenzen für Alphabete, die eine Anzahl von Zeichen haben, die no eine Potenz von zwei.

Für Alphabete mit 2^k Zeichen ist die Berechnung von de Bruijn-Sequenzen einfach: Es gibt einige einfache Regeln, wie zum Beispiel "Bevorzugen Sie Einsen" und "Bevorzugen Sie Gegensätzliches" die für die Erzeugung von B(2,n) funktionieren. B(2^k,n) ist genau dasselbe wie B(2,kn), wenn Sie die 1en und 0en als Binärcodes für die tatsächlichen Zeichen in Ihrem Alphabet lesen. So kann man z. B. B(2,8n) als eine Folge von Bytes mit der Länge n interpretieren.

Prefer Ones ist ganz einfach: Schreibe n Nullen. Schreiben Sie dann immer eine Eins, es sei denn, sie würde die Wiederholung einer n-langen Zeichenkette verursachen; andernfalls schreiben Sie eine Null.

Derzeit sehe ich nicht, wie man solche Regeln auf Alphabete verallgemeinern kann, die nicht die Größe einer Zweierpotenz haben.

Es gibt eine allgemeine Methode zur Berechnung von de Bruijn-Folgen über Graphen: Jede Sequenz der Länge n, die durch Ihr Alphabet erzeugt wird, sei ein Knoten; legen Sie eine Kante von A nach B, wenn die äußersten rechten n-1 Zeichen von A die gleichen sind wie die äußersten linken n-1 Zeichen von B. Beschriften Sie jede Kante mit dem letzten Zeichen der Zeichenkette im Kopfeck. Jede Eulerscher Pfad durch diesen Graphen wird eine de Bruijn-Sequenz erzeugen, und die besondere Konstruktion, die wir verwendet haben, garantiert, dass es mindestens einen solchen Pfad gibt. Wir können verwenden Fleurys Algorithmus um (nicht-deterministisch) einen Eulerschen Pfad zu konstruieren:

1. Wählen Sie einen Scheitelpunkt.
2. Verlassen Sie diesen Knoten über eine Kante und löschen Sie diese Kante, wobei Sie nur solche Kanten wählen, deren Löschung den Knoten vom Graphen trennen würde, wenn es keine Alternative gibt.
3. Fügen Sie die Bezeichnung der soeben gelöschten Kante an Ihre Zeichenfolge an.
4. Gehen Sie zu 2, bis alle Kanten verschwunden sind.

Die resultierende Zeichenkette ist eine de Bruijn-Sequenz.

Dieser Algorithmus ist etwas komplexer zu implementieren als Prefer Ones. Die Einfachheit von Prefer Ones besteht darin, dass man nur die bereits erzeugte Ausgabe zu Rate ziehen muss, um zu entscheiden, was zu tun ist. Gibt es eine einfache Möglichkeit, Prefer Ones (oder möglicherweise Prefer Opposites) auf Alphabete zu verallgemeinern, die nicht die Potenz von zwei haben?

Answer 1

Dies ist meine C++-Implementierung des Algorithmus in Abbildung 1 aus eine Arbeit von Sawada und 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;

Die vollständige Referenz für das Papier lautet: Joe Sawada und Frank Ruskey, "An Efficient Algorithm for Generating Necklaces with Fixed Density", SIAM Journal of Computing 29 :671-684, 1999.

Answer 2

Nach Angaben von diese Webseite in der kombinatorischen Gruppe des Fachbereichs CS an der UVic gibt es ein Ergebnis, das auf Fredericksen zurückgeht und besagt, dass man eine de Bruijn-Folge (die lexikografisch kleinste) erzeugen kann, indem man "die lexikografische Folge von Lyndon Wörter mit durch n teilbaren Längen". Es gibt sogar Quellcode zum Erstellen der Sequenz, den Sie anfordern können.

Answer 3

Sind Sie nur an einer Verallgemeinerung von Prefer Ones interessiert oder wollen Sie einfach einen nicht so komplexen Algorithmus? Wenn Letzteres zutrifft, könnte Ihnen vielleicht die rekursive Implementierung von Frank Ruskey weiterhelfen.

Vor einem Jahr Ich habe das übersetzt zu 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 stellte fest, dass die alike bewirkt nichts. Das folgende Beispiel erzeugt die gleiche Sequenz.

@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

Oder Sie können verwenden:

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

Der Algorithmus von Duval macht dasselbe iterativ (diesmal in 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))