Konvertieren von N -Zeichenfolgen in eine gemeinsame Zielzeichenfolge in maximal k

Question

Ich habe eine Reihe von String [S1 S2 S3 ... Sn] Und ich bin, um all diese Zielsaiten zu zählen T so dass jeder von jedem von S1 S2... Sn kann in konvertiert werden in T innerhalb von insgesamt K Änderungen.
Alle Saiten sind von fester Länge L Und eine Bearbeitung hier ist Hamming -Entfernung.

Alles was ich ist eine Art Brute -Force -Ansatz. Wenn meine Alphabetgröße 4 beträgt, habe ich einen Abtastraum von O (4^l) und es braucht O (l) Zeit, um jeden von ihnen zu überprüfen. Ich kann die Komplexität nicht von Exponential zu einem Poly- oder Pseudo-Poly senken! Gibt es eine Möglichkeit, den Stichprobenraum abzubauen, um es besser zu machen?

Ich habe versucht, es wie im l-dimensionalen Vektorraum zu visualisieren. Ich habe N -Punkte gegeben und muss alle Punkte zählen, deren Abstand von den angegebenen N -Punkten kleiner oder gleich K ist.
i.e. d1 + d2 + d3 +...+ dN <= K
Gibt es einen bekannten geometrischen Algorithmus, der dieses oder ähnliches Problem mit einer besseren Komplexität löst? Bitte zeigen Sie mich in die richtige Richtung, oder irgendwelche Hinweise werden geschätzt.
Vielen Dank

Answer 1

Sie können dies effizient mit dynamischer Programmierung tun.

Die wichtigste Idee ist, dass Sie nicht alle möglichen Zielzeichenfolgen aufzählen müssen. Sie müssen nur wissen, wie viele Möglichkeiten Ziele mit k -Änderungen möglich sind, wenn nur die Zeichenfolge nach IN I.

alphabet = 'abcd'
s = [ 'aabbbb', 'bacaaa', 'dabbbb', 'cabaaa']

# use memoized from http://wiki.python.org/moin/PythonDecoratorLibrary          
@memoized
def count(edits_left, index):
  if index == -1 and edits_left >= 0:
    return 1
  if edits_left < 0:
    return 0
  ret = 0
  for char in alphabet:
    edits_used = 0
    for mutate_str in s:
      if mutate_str[index] != char:
        edits_used += 1
    ret += count(edits_left - edits_used, index - 1)
  return ret

Answer 2

Wenn ich laut nachdachte, scheint es mir, dass dieses Problem auf ein kombinatorisches Problem hinausgeht.

Im Allgemeinen gibt es für eine Länge von L -Länge l insgesamt c (l, k) (binomiale Koeffizienten) Positionen, die ersetzt werden können Entfernung von K.

Der Binomialkoeffizient kann mit dynamischer Programmierung und dem Pascal -Dreieck ganz einfach berechnet werden ... keine Notwendigkeit, verrückt nach faktoriel usw. zu werden ...

Jetzt, da ein String -Fall behandelt wird, ist der Umgang mit mehreren Zeichenfolgen etwas schwieriger, da Sie möglicherweise Ziele doppelt zählen. Wenn S1 weit von S2 entfernt ist, generiert Sie jedoch, dass die gleiche Zielgruppe in diesem Fall nicht doppelt zählt. Diese letzte Aussage könnte ein langer Schuss sein, deshalb habe ich darauf geachtet, "intuitiv" zu sagen :) :)

Ich hoffe es hilft,