Ich habe an meiner Arbeit an Gruppierungsproblemen gearbeitet. Es gibt einige Fragen, bitte, ertragen Sie mit mir. Ich finde sie ziemlich interessant. Wenn jemand hier auch Interesse an Kombinatorik hat, helfen Sie mir bitte.
Ok, wir haben eine Menge Charaktere, hier habe ich ein i d s genommen.
Wie können wir die Elemente gruppieren? Sagen wir, wir haben 4 Zeichen a i d s. Gültige Gruppen (unter Beibehaltung der Reihenfolge) wären:
a i d s
ein i ds
eine ID s
ai ds
ai ds
a ids
Hilfe s
Hilfsmittel
Wie listen Sie alle Gruppen auf? Können Sie mir sagen, wie viele Kombinationen es für n Buchstaben gibt?
2. Sonderfälle
Was ist, wenn der Fall einen Unterschied macht, wie Ai sd und ai sd zwei Gruppen sind?
Wie viel Zeit würden Sie brauchen, um alle Fälle aufzuzählen? Wie groß wäre der Zeitunterschied zwischen dem Fall mit 4 Buchstaben und 5 Buchstaben?
Wenn Sie das "Leerzeichen" als Zeichen verwenden. Nach wie vielen Aufzählungen hätten Sie geschrieben?
Wenn Sie eine Transformation von einem Wort zu einem anderen Wort als Entfernung definieren. Sagen Sie "ai ds" und "a i ds" hat 1 Abstand, weil Sie den Buchstaben "i" um einen Schritt verschieben sollten. Könntest du die Wörter auf jeder Seite eines Wortes in n Entfernung finden?
Bearbeiten:
"aids" ist ein einzelnes Wort.
"a ids" "aid s" sind zwei Wörter, die in einem Abstand von dem ursprünglichen Wort "aids" stehen.
"a id s" ist ein Wort, das zwei Abstand vom ursprünglichen Wort "aids" entfernt ist.
"a i d s" ist ein Wort, das drei Abstand vom Wort entfernt ist.
Dieses Problem scheint Goldminen zu sein.
Bonus: Was ist der kleinste Abstand zwischen zwei Wörtern? Wie "Aids" ist eine Entfernung von "a ids" und auch zwei Entfernung. Gibt es ein "Mittelpunkt" -Wort, von dem aus Sie mit der geringsten Entfernung ein beliebiges anderes Wort in der Aufzählung erreichen können? Wie viele Wege gibt es von einem Wort zum anderen?
Die Anzahl der Kombinationen zu berechnen ist trivial. Grundsätzlich haben Sie ein Zeichen zwischen jeweils zwei Buchstaben. Es könnte "Epsilon" (leer) oder Raum sein. Also haben Sie für n Buchstaben n-1 solche Trennzeichen. Da jedes Zeichen nur zwei Werte haben kann, entspricht das einer Binärzahl von n-1 Ziffern. So können Sie 2 zu der Kraft von n-1 Kombinationen haben.
%Vor%Nun, für die speziellen Fälle. Wenn jedes Zeichen sowohl Klein- als auch Großbuchstaben sein kann, sind das 2 verschiedene Varianten der Zeichen (solange sie Buchstaben sind). Nun, JEDE Kombination oben hat 2 n Variationen basierend auf der Großschreibung, also ist das Endergebnis (2 (n-1)) * (2 ** n), was 2 ** entspricht (2 * n -1).
Für jeden zusätzlichen Buchstaben verdoppelt oder vervierfacht man (abhängig von der Großschreibung) die Zeit, die für die Aufzählung benötigt wird, wie aus der Formel leicht zu verstehen ist.
Die Gesamtzahl der Zeichen ist ein bisschen schwieriger, aber es genügt zu bemerken, dass jedes "Leerzeichen" die Hälfte der Zeit "Epsilon" ist. Also haben wir (2 ** (n-1)) * n (Buchstaben) + ((2 ** (n-1)) * (n-1)) / 2 (Leerzeichen). Im Beispiel:
%Vor%Schließlich hängt das Entfernungsproblem mit der Levenshtein-Entfernung zusammen. Ich dachte darüber nach, einen Burkhard-Keller-Baum zu benutzen, aber ich Jetzt ist das überhaupt nicht nötig, da das Problem etwas einfacher ist.
Erstens wird die minimale Anzahl von Einfügungen / Löschungen / Änderungen, die notwendig ist, um eine Zeichenkette gleich einer anderen zu machen, als Levenshtein distance . Dies ist direkt auf das Problem anwendbar: Sie fügen Leerzeichen hinzu, löschen Leerzeichen und ändern Groß- / Kleinschreibung nach Bedarf. In der Regel wird dies am besten mit Dynamic Programming gelöst, was im Allgemeinen als das Aufbewahren von Daten über die Lösung zu kleinen Teilen angesehen werden kann das Problem, das dann wiederverwendet wird, um andere Teile / größere Teile zu berechnen.
Aber angesichts der besonderen Einschränkungen unseres Problems können wir einfach die "binären" Zahlen vergleichen, die spaces / epsilon darstellen.
Sagen Sie, eine Funktion f (Wort) gibt die Binärzahl zurück, die Leerzeichen in diesem Wort darstellt. Zum Beispiel gibt es "010" für "ai ds" und "111" für "a i d s" zurück. Die Anzahl der Änderungen zwischen jeder Kombination wird durch XOR der Ergebnisse von f (010 x oder 111 = 101) und dann durch Zählen der Anzahl der Bits gleich 1 gegeben. Lassen Sie uns ein paar Funktionen in Scala dafür schreiben:
%Vor%Nun ist der Vergleich von Groß- und Kleinbuchstaben ziemlich einfach, wenn wir Leerzeichen wegwerfen:
%Vor%Also ist die Levenshtein-Distanz:
%Vor%Wir kennen auch die folgenden Eigenschaften von Levenshtein. Sage d (x, y) ist der Levenshtein-Abstand zwischen x und y. Dann wissen wir:
%Vor%Das letzte Kriterium, das ich als Dreiecksungleichheit bezeichne. Einfach ausgedrückt ist der Pfad von x zu z mindestens so klein wie der Pfad von x nach y plus der Pfad von y nach z (denke ein Dreieck mit den Scheitelpunkten x, y und z).
Ok, also lasst uns über die Bonusfragen nachdenken.
Wie viele Pfade gibt es zwischen zwei Wörtern? Nun, wenn die Levenshtein-Distanz n ist, bedeutet das, dass du "n" einzigartige Modifikationen hast, a1, a2, ..., an. Für jede unterschiedliche Reihenfolge dieser Änderungen haben Sie einen Pfad. Die Anzahl der Permutationen von "n" Elementen ist die Fakultät von "n" (oder n!):
%Vor%Gibt es eine "zentrale" Kombination? Eigentlich nein. Wenn wir zurückgehen und Kombinationen als Paare von Binärzahlen vorstellen, die die Leerzeichen / Leerstellen und Groß- / Kleinbuchstaben darstellen, dann sollte es offensichtlich sein, dass Sie die Bits einfach invertieren können, um eine neue Kombination zu erzeugen, deren Entfernung zu der gewählten ist maximal möglich.
Oder, mit anderen Worten, für jede Kombination von n Buchstaben gibt es eine und nur eine entsprechende Kombination, so dass der Levenshtein-Abstand zwischen den beiden Kombinationen 2 * n - 1 ist, der maximal mögliche Abstand zwischen zweien Kombinationen.
Ich sehe, dass ich vergessen habe, alle Kombinationen zu berechnen, deren (minimaler) Abstand zu s n ist. Nun, wir wissen, dass jede Kombination als zwei Binärzahlen dargestellt werden kann, die die Leerstellen und die Großschreibung jedes Buchstabens darstellen, wobei der erste n-1 Ziffern lang und der zweite n Ziffern lang ist.
Wir wissen auch, dass wir einfach jede dieser "Ziffern" invertieren können, um einen Unterschied zu erhalten. Also, wenn wir eine große binäre Zahl 2 * n - 1 Ziffern lang bekommen, und wir alle ihre Ziffern aufzählen, werden die Kombinationen mit einem minimalen Abstand d von der Kombination der 2 * n-1 Ziffern in Gruppen von Größe gegeben "d" ohne Wiederholungen. Für N = 2 * n-1 ist die Anzahl einer solchen Kombination N! / ((N - d)! * D!).
Zum Beispiel für Abstand 2 und "Hilfsmittel", n = 4, d = 2, N = 2 * 4-1 = 7, und die Anzahl der Kombinationen ist 7! / (5! * 2!) = 7 * 6/2 = 21.
Wir können die Kombinationen so zusammenstellen:
%Vor%Dadurch werden Listen mit zu ändernden Buchstaben / Leerzeichen zurückgegeben. Wir geben an, welcher Buchstabe oder Platz sich ändern muss, durch die Nummer des Bits, das wir umschalten möchten. Um die Dinge zu vereinfachen, nehmen wir an, dass die binäre Zahl für die Groß- und die binäre Zahl für den Raum / kein Leerzeichen in einer einzelnen Binärzahl verkettet sind.
Als nächstes müssen wir einen Weg finden, die Variationen aus diesen Informationen zu erzeugen. Die Groß- / Kleinschreibung ist einfach, vorausgesetzt, wir erhalten das Wort ohne Leerzeichen:
%Vor%Das Umschalten von Räumen ist schwieriger. Wir werden spacesToBinary verwenden, wie oben definiert, das in eine Liste von gesetzten Bit-Zahlen umwandeln, die angeforderten Bits umschalten und diese zurückgeben. Anschließend verwenden wir eine andere Funktion, um die Leerzeichen an den richtigen Stellen einzufügen:
%Vor%Nun müssen wir die Raumdifferenz berechnen, die Leerzeichen entfernen, die Groß- und Kleinschreibung ändern und dann die Leerzeichen hinzufügen. Mal sehen:
%Vor%Schließlich berechnen wir alle Kombinationen und erzeugen dann für jede eine modifizierte Zeichenkette:
%Vor%Dieser Code wurde allesamt auf Scala 2.8 getestet (abgesehen von einigen Umbenennungen, die ich gerade gemacht habe). Hier ist das Ergebnis eines Laufs:
%Vor%Wie die anderen Antworten schon gesagt haben, gibt es 2 ^ (n-1) Möglichkeiten für Punkt 1. Über einige der Spezialfälle (Punkt 2):
Nun, in diesem Fall hatten Sie 2 ^ n verschiedene Fallkombinationen, also hatten Sie überhaupt 2 ^ n * 2 ^ (n-1) = 2 ^ (2 * n - 1) Möglichkeiten.
Das ist eine interessantere Frage. Sie haben 1 Möglichkeit, keinen Platz zu platzieren, 3 Möglichkeiten, 1 Platz zu platzieren, 3 Möglichkeiten, 2 Räume zu platzieren und 1 Möglichkeit, 3 Räume zu platzieren. Dies ist eine Binomialverteilung, wenn ich mich richtig erinnere, und es gibt Formeln, um die Zahlen zu berechnen. Sie können dazu auch Pascals Dreieck verwenden:
%Vor%Nachdem Sie diese Zahlen erhalten haben, berechnen Sie die Gesamtzahl der Zeichen wie folgt:
%Vor%Ссылка (Ghostscript / Ghostview herunterladen, wenn Postscript nicht angezeigt werden kann) diskutiert Partitionen im Detail.
Für eine Sequenz der Länge n gibt es 2 ^ (n-1) Partitionen. Stellen Sie sich ein bisschen zwischen jedem Paar aufeinander folgender Gegenstände vor. Wenn das Bit gesetzt ist, werden sie getrennt (durch ein Leerzeichen, wie Sie sie aufgelistet haben). "Aids" (Länge 4) hat 2 ^ 3 mögliche Partitionen.
Als Antwort auf Ihre anderen Fragen:
Zeit zum Aufzählen: O (n * 2 ^ n) - Konstante in der Länge der Ausgabe. Die Anzahl der Elemente erhöht sich nicht nur mit der Eingabedauer, sondern auch die Anzahl der Zeichen in jedem Element.
Anzahl der geschriebenen Zeichen: Wir zählen keine Zeilenumbrüche (wenn Sie dies tun, fügen Sie weitere 2 ^ (n-1) Zeichen hinzu). Dann haben Sie n * 2 ^ (n-1) Nicht-Leerzeichen-Zeichen plus die Anzahl von 1s in allen eindeutigen n-1-stelligen Bit-Zeichenfolgen. Die k Bit-Zeichenketten haben, wenn sie ausgeschrieben sind, k * 2 ^ k Bits und die Hälfte davon sind 1. Somit ist die Gesamtzahl der Zeichen [n + (n-1) / 2] * 2 ^ (n-1) ), Newlines nicht mitgerechnet. In deiner Liste der 8 Variationen zu "Aids" gibt es 32 Leerzeichen und 12 Leerzeichen - 4 * 2 ^ 3 bzw. (3/2) * 2 ^ 3.
Entfernung bearbeiten: Sie müssen genauer über die Transformationen und deren Kosten sein. Mit "Wort" nehme ich an, Sie meinen eine einzelne Partition (eine Ihrer 8 Beispielzeilen). Wenn ein Edit das Entfernen oder Hinzufügen eines einzelnen Leerzeichens ist, dann sprechen Sie über die Hamming-Distanz auf n-1 Bit-Strings.
Ein einfacher Algorithmus zum Aufsuchen jedes der Wörter innerhalb der Distanz k oder weniger: Verwenden einer Hash-Tabelle, um jede Bitfolge nur einmal zu besuchen (oder ein Array von 2 ^ (n-1) Bits, aber das kann zu groß sein), rekursiv jeden der benachbarten Single-Edit-Unterschiede (unter der Annahme Hamming-Abstand: für i von 1 .. (n-1), XOR 2 ^ i mit der Source-Bitstring, Umschalten des i-ten Bit).
Mach das bis zu einer Tiefe von k (die Tiefe wird zusammen mit deiner Rekursion weitergegeben), und du hast alle Bearbeitungen innerhalb der Distanz k besucht. Natürlich, wenn Sie genau diejenigen mit genau der Tiefe k wollen, sollten Sie die Breite der ersten Suche verwenden: anstatt jeden Nachbarn sofort zu besuchen, halten Sie sie in einer Warteschlange, um besucht zu werden. Während Sie die Warteschlange für Objekte einer bestimmten Generation (j) besuchen (alle haben den gleichen Bearbeitungsabstand), ordnen Sie zukünftige Objekte in einer anderen Warteschlange für die nächste Generation (j + 1) an. Auf diese Weise besuchen Sie jeden String zuerst mit der geringstmöglichen Anzahl von Bearbeitungen (Breite zuerst = beste zuerst, wenn jeder Übergang die gleichen Kosten hat).
Wenn Sie die erste Suche nicht ausführen möchten, können Sie die Menge der Wörter innerhalb von k oder weniger und die Menge innerhalb von k-1 oder weniger berechnen und die Differenz verwenden (Sie würden zwei separate verwenden Tabellen). Dies ist effektiv "iterative Vertiefung der Suche".
B-K-Bäume sind hier nicht geeignet, es sei denn, Sie denken an einen unstrukturierten Satz von Wörtern (ein allgemeines Wörterbuch). Wir kennen die Struktur der Partitionen für ein einzelnes Wort bereits genau.
Die Zählargumente sind richtig.
Es gibt eine generelle Art, wie ich Probleme wie diese mit Hilfe von Branch-and-Bound programmieren kann. Hier ist ein Beispiel.
Anstatt eine Schleife zu schreiben, um die Zeichenfolge zu scannen, schreiben Sie eine rekursive Funktion und verfolgen die Kosten als eines ihrer Argumente. Dann können Sie bei jedem Schritt 1) die Zeichenkette um einen zusätzlichen Wert von Null verkleinern, dann 2) eine kleine Änderung an der Zeichenkette vornehmen, ein Inkrement zu den Kosten hinzufügen und dann einen Schritt vorwärts machen und 3) 2 für wiederholen so viele verschiedene Arten von Änderungen, die Sie berücksichtigen möchten.
Dann haben Sie ein Gesamtkostenbudget und weigern sich, eine Niederlassung zu nehmen, wo die Kosten das Budget überschreiten würden.
Schließlich, als eine äußere Schleife, mach das Ganze einmal mit einem Budget von 0. Wenn das keine Übereinstimmungen erzeugt, tu es erneut mit Kosten von 1, und so weiter, bis du ein oder mehrere Übereinstimmungen erhältst.
Tags und Links algorithm string math computer-science combinatorics