, und sind zwei Zeichenfolgen gleicher Länge. Eine Darstellung von zwei Zeichenfolgen ist eine bijektive Abbildung von so dass für jedes .b 1 b 2 … b na i = b p ( i ) i
Es kann mehr als ein Diagramm für dasselbe Zeichenfolgenpaar geben. Zum Beispiel, wenn `abcab` und wir haben und unter anderem.b = p 1 [ 1 , 2 , 3 , 4 , 5 ] → [ 4 , 5 , 1 , 2 , 3 ] p 2 [ 1 , 2 , 3 , 4 , 5 ] → [ 2 , 5 , 1 , 4 , 3 ]cabab
Wir werden sagen, dass das Gewicht eines Anagramms die Anzahl der Schnitte ist, die in der ersten Zeichenfolge ausgeführt werden müssen, um Blöcke zu erhalten, die neu angeordnet werden können, um die zweite Zeichenfolge zu erhalten. Formal ist dies die Anzahl der Werte von für die . Das heißt, er die Anzahl der Punkte ist , bei der ist nicht durch genau 1.Bei Beispiel erhöhen, und , da schneidet einmal in die Brocken und und p_2 Schnitte vier mal in fünf Stücke.12345
123
45
12345
Angenommen, es gibt ein Anagramm für zwei Zeichenfolgen und . Dann muss mindestens ein Anagramm das geringste Gewicht haben. Nehmen wir an, dies ist das leichteste . (Möglicherweise gibt es mehrere leichteste Anagramme. Das ist mir egal, da ich nur an den Gewichten interessiert bin.)
Frage
Ich möchte einen Algorithmus, der bei zwei Strings, für die ein Anagramm existiert, effizient das genaue Gewicht des leichtesten Anagramms der beiden Strings ergibt . Es ist in Ordnung, wenn der Algorithmus auch ein leichtestes Diagramm liefert, muss es aber nicht.
Es ist ziemlich einfach, alle Anagramme zu generieren und zu wägen, aber es kann viele geben, daher würde ich eine Methode bevorzugen, die leichte Anagramme direkt findet.
Motivation
Der Grund, warum dieses Problem von Interesse ist, ist folgender. Es ist sehr einfach, den Computer das Wörterbuch durchsuchen zu lassen und Anagramme zu finden, Wortpaare, die genau dieselben Buchstaben enthalten. Viele der erstellten Anagramme sind jedoch uninteressant. Die längsten Beispiele im zweiten internationalen Wörterbuch von Webster sind:
Cholezystoduodenostomie
Duodenocholezystostomie
Das Problem sollte klar sein: diese uninteressant sind , weil sie einen sehr leichten Anagrammieren dass einfach tauscht die zugeben cholecysto
, duedeno
und stomy
Abschnitte, bei einem Gewicht von 2. Andererseits ist diese viel kürzer Beispiel ist viel mehr überraschend und interessant:
Küste
Schnitts
Hier hat das leichteste Diagramm das Gewicht 8.
Ich habe ein Programm, das diese Methode verwendet, um interessante Anagramme zu lokalisieren, und zwar solche, für die alle Anagramme ein hohes Gewicht haben. Dies geschieht jedoch durch Generieren und Abwägen aller möglichen Anagramme, was langsam ist.
quelle
cholecystoduodenostomy
istccddeehlmnooooossttuyy
.) Zwei Worte Anagramme sind , wenn und nur wenn sie die gleiche kanonische Form haben. Sie speichern die Wörter in einer Hash-Tabelle, die durch ihre kanonischen Formen gekennzeichnet ist. Wenn Sie eine Kollision finden, erhalten Sie ein Anagramm.Antworten:
Dieses Problem wird als "minimales gemeinsames String-Partitionsproblem" bezeichnet. (Genauer gesagt entspricht die Antwort in dem minimalen gemeinsamen String-Partitionsproblem der Antwort in Ihrem Problem plus 1.) Leider ist es NP-schwer, selbst mit der Einschränkung, dass Jeder Buchstabe kommt höchstens zweimal in jeder der Eingabezeichenfolgen vor, wie Goldstein, Kilman und Zheng [GKZ05] beweisen. Dies bedeutet, dass kein Polynomzeitalgorithmus existiert, es sei denn, P = NP. (Wenn natürlich jeder Buchstabe höchstens einmal vorkommt, ist das Problem trivial, da es nur ein Anagramm gibt.)
Positiv zu vermerken ist, dass dieselben Autoren [GKZ05] unter derselben Einschränkung einen Algorithmus zur Näherung der Polynomzeit 1.1037 angeben. (Ein "1.1037- Näherungsalgorithmus " bedeutet einen Algorithmus, der möglicherweise nicht die richtige Antwort A ausgibt, aber garantiert einen Wert B ausgibt, so dass A ≤ B ≤ 1.1037 A. ) Sie geben auch einen linearen 4-Näherungsalgorithmus unter schwächere Einschränkung, dass jeder Buchstabe höchstens dreimal in jeder der Eingabezeichenfolgen vorkommt.
[GKZ05] Avraham Goldstein, Petr Kolman und Jie Zheng. Minimales allgemeines String-Partitionsproblem: Härte und Approximationen. Electronic Journal of Combinatorics , 12, Artikel R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50
quelle
Dies ist eine Fortsetzung der obigen Antwort von Tsuyoshi Ito , die den wichtigsten Teil des von ihm zitierten GKZ05-Papiers zusammenfasst .
Das Papier zeigt eine Reduktion auf das Problem des Maximal Independent Set ( MIS ). Konstruieren Sie einen Graphen dessen Eckpunkte Paare ( i , j ) sind, so dass a i = b j und a i + 1 = b j + 1 . Verbinden Sie die Eckpunkte ( i , j ) und ( k , ℓ ) (wobei i ≤ k ist ) mit einer Kante, wenn es unmöglich ist, dass ein Anagramm alle i abbildetG (i,j) ai=bj ai+1=bj+1 (i,j) (k,ℓ) i≤k und i + 1 ↦ j + 1 und k ↦ l und k + 1 ↦ l + 1 . Dies ist leicht zu erkennen; Eine solche Zuordnung ist nicht möglich, wenn eine der folgenden Bedingungen erfüllt ist:i↦j i+1↦j+1 k↦ℓ k+1↦ℓ+1
Angenommen, der resultierende Graph hat eine maximale unabhängige Menge von Größen s . Dann ist das minimale Anagrammgewicht genau n - s - 1 , wobei n die Länge der Saiten a und b ist . (Die Umkehrung gilt auch: Ein Anagramm mit geringem Gewicht wird direkt in ein großes MIS für G übersetzt . Einzelheiten finden Sie auf den Seiten 4–5 des Papiers.)G s n−s−1 n a b G
Betrachten Sie zum Beispiel die beiden Zeichenfolgens=2
yttrious
undtouristy
. Der entsprechende Graph hat zwei Eckpunkte, einen für das gemeinsameou
Paar und einen für das gemeinsameri
Paar. Es gibt keine Kante zwischen den Scheitelpunkten, da es möglich ist, ein Diagramm zu erstellen, das sowohlou
aufou
als auchri
aufri
abgebildet wird. oder man kann überprüfen, ob die drei Bedingungen vor allem scheitern. Der Graph hat also offensichtlich ein MIS der Größe und das minimale Anagrammgewicht ist in der Tat 8-2-1 = 5, entsprechend dem Anagramm ↔ . 'y|t|t|ri|ou|s
t|ou|ri|s|t|y
Auf der anderen Seite betrachten
derater
undtreader
. Dieses Mal hat das Diagramm drei Eckpunkte:DErater
+treaDEr
dERater
+treadER
deratER
+treadER
2 und 3 sind nicht kompatibel, und 1 und 3 sind nicht kompatibel, aber 1 und 2 sind kompatibel. Das eindeutige MIS hat also die Größe und enthält die Eckpunkte 1 und 2. Die entsprechende Darstellung des Gewichts 7-2-1 = 4 ist ↔ .s=2
der|a|t|e|r
t|r|e|a|der
quelle
Es geht nicht um den genauen Algorithmus, den Sie sich vorgestellt haben (die Antwort von Tsuyoshi Ito ), sondern darum, das zugrunde liegende Problem zu lösen, "interessante" Anagramme zu finden ...
Mein erster Gedanke war, eine Variation der Bearbeitungsentfernung zu verwenden, bei der die atomaren Änderungen eher nach ihrer "Interessantheit" als nach den üblichen "Schwierigkeits" - oder "Verwirrbarkeit" -Gewichten gewichtet werden. Natürlich ist es unwahrscheinlich, dass Sie die wirklich interessanten Transformationen auf diese Weise effizient codieren können, da sie wahrscheinlich nicht lokal sind und daher in die NP-vollständigen Probleme von MIS usw. geraten.
Der zweite Gedanke wäre also, eine Buchstaben-zu-Buchstaben-Ausrichtung zwischen den Wörtern zu konstruieren (à la maschinelle Übersetzungsausrichtungen) und dann die Ausrichtungen selbst auf "Interessantheit" zu bewerten (z. B. die Ausrichtungen zu zählen, die benachbarte Buchstaben zu Nicht-Buchstaben machen). benachbarte Buchstaben oder wie viele Ausrichtungen jede Ausrichtung kreuzt usw. und kombinieren Sie sie dann alle über ein loglineares Modell oder so).
Die dritte Idee besteht darin, den Blick auf die Struktur des Anagramms selbst vollständig aufzugeben und stattdessen die Semantik der Wörter zu betrachten. Was ein Anagramm oft "interessant" macht, ist die Inkongruenz zwischen den Bedeutungen der beteiligten Wörter. Versuchen Sie also etwas wie die Berechnung der Entfernung in WordNet oder ähnliches.
quelle
Das Problem kann in Form von Permutationsgruppen formuliert werden .
Nun enthält eine Permutationsgruppe alle "Anagrammzüge", sowohl primitiv (Vertauschen von zwei Buchstaben) als auch zusammengesetzt aus Sequenzen primitiver Züge. Es scheint, dass Sie nur an einer Teilmenge der möglichen Permutationen interessiert sind. Ich werde versuchen, diese zu definieren.
Erinnern Sie sich zunächst an die Notation für Permutationen, nämlich die sogenannte Zyklusnotation :
Diese einfachen 'Zyklen' beschreiben komplexere Permutationen.
Diese Bewegungen bilden die Grundlage für Ihren Algorithmus. Was Sie interessiert, ist, die kleinste Sequenz dieser Bewegungen zu finden, um von einem Wort zum nächsten zu gelangen.
Ich kenne keinen Algorithmus, um dies zu berechnen, abgesehen von der Brute-Force-Suche, aber zumindest gibt es jetzt eine klarere (ich hoffe) Beschreibung der primitiven Bewegungen. (Und vielleicht kann ein Gruppentheoretiker unter uns auf einen geeigneten Algorithmus verweisen.)
quelle
Bei der Cholezystoduodenostomie / Duodenocholezystostomie stelle ich fest, dass Sie, wenn Sie jedem Zeichen eine Nummer zuweisen, die beschreibt, um wie viel es sich als Delta bewegt hat, etwas wie 7 7, dann 8 -7, dann 6 0 haben. Das ist nicht richtig, da einige Zeichen möglicherweise wiederholt wurden (das zweite c wurde nur um 2 vorwärts und nicht um 7 rückwärts verschoben), aber immer noch sehr "lauflängencodierbar", da Sie dieselben Deltas in einer Reihe sehen.
Vergleiche mit Küste / Abschnitt, wo du so etwas wie (+2) (+ 5) (+ 5) (- 3) (- 1) (+ 3) siehst .... viel weniger "Lauflänge codierbar".
Vielleicht könnte Ihnen die Zufälligkeit der Deltas eine "Punktzahl" darüber geben, wie interessant das Anagramm ist?
quelle