Alle * perfekten Pangrams des Englischen

An Englisch Pangram ist ein Satz, der alle 26 Buchstaben des englischen Alphabets enthält. Das bekannteste englische Pangram ist wahrscheinlich „Der schnelle braune Fuchs springt über den faulen Hund“. Mein Lieblingspangram ist „Erstaunlicherweise bieten nur wenige Diskotheken Jukeboxen an.“

Ein perfektes Pangram ist ein Pangram, bei dem jeder der Buchstaben erscheint nur einmal. Ich habe online einige Quellen gefunden, die die bekannten perfekten Pangrams auflisten. Niemand scheint sich erfolgreich bemüht zu haben, alle erschöpfend zu produzieren, deshalb habe ich es als lustige Herausforderung angenommen. So fand ich alle * perfekten Pangrams des Englischen. Ich werde das Sternchen später erklären.

• Crwth vox zaps qi gym fjeld bunk. (Der Klang einer keltischen Geige trifft ein Fitnesscenter, das sich auf östliche spirituelle Kräfte konzentriert und sich in einem kargen Plateau Skandinaviens befindet.) Dies sind alles juristische Wörter von Scrabble!
• Squdgy kilp job zarf nth cwm vex. (Der schlecht geformte Seetang kauft einen Zierbecherwärmer, den eine der vielen halboffenen steilen Mulden an der Spitze eines Tals oder Berges gereizt hat.)
• Jocknymphen waqf drug vex blitz. (Die gemeinnützige Stiftung berauschte die Waldgeister, die den Athleten frustrierten, der einen Angriff unternahm.)
• Hm, Fjordwalzer, Cinq Busk, Pyx Veg. (Mal sehen, ein langer, schmaler, tiefer Einlass tanzt, die fünf auf den Würfeln machen Musik auf der Straße und der kleine runde Behälter für die Kranken und Unfähigen ruht.) Auch Scrabble legal, hat aber eine Interjektion (Hm).

Leider sind dies einige der lesbarsten Sätze, die ich finden konnte *. Alle perfekten Pangrams, die aus der offiziellen Turnier- und Club-Wortliste 3 (OWL3) für Scrabble ohne Interjektionen generiert wurden, enthalten entweder das Wort cwm oder crwth. Waqf ist außerhalb Nordamerikas für Scrabble-Turniere legal.

So finden Sie alle perfekten Pangrams

Die Methode zum Finden perfekter Pangrams erfolgt in zwei Schritten. Die erste besteht darin, alle Sätze von Wörtern zu finden, die jeden Buchstaben des englischen Alphabets einmal enthalten. Der zweite Schritt besteht darin, herauszufinden, welche dieser Sätze in gültige englische Sätze umgeordnet werden können.

Schritt 1: Suchen von Wortgruppen für das perfekte Pangram

Beginnen Sie mit der Suche nach Wortgruppen, die Für das englische Alphabet ist eine Liste englischer Wörter erforderlich. Es war viel schwieriger als erwartet, eine qualitativ hochwertige Liste von Wörtern zu finden und zu pflegen. Ursprünglich dachte ich, dass dieses Projekt zwei Tage dauern würde, aber aufgrund dieses Datenqualitätsproblems dauerte es zwei Wochen.

Ich begann mit dem Unix-Wörterbuch, einer frei verfügbaren Liste englischer Wörter Das kommt mit fast allen Unix-basierten Betriebssystemen. Ich bemerkte sofort, dass die Liste Qualitätsprobleme hatte. Erstens wurde jeder Buchstabe des Alphabets als Wort im Unix-Wörterbuch betrachtet und enthielt viele Nichtwörter wie „vejoz“. Dies zeigte die Notwendigkeit einer schwarzen Liste zur Verwaltung der online gefundenen Wortlisten Im Unix-Wörterbuch fehlten Pluralformen für Wörter, daher würde das Wörterbuch das Wort „orange“, aber nicht „Orangen“ enthalten. Die Wortliste ist in der Tat so restriktiv, dass keine bisher bekannten perfekten Pangrams nur Wörter aus dem Unix-Wörterbuch enthalten. Ich fand sie immer noch Einige, wie „squdgy kilp job zarf nth cwm vex“.

Ich wandte mich dann dem Internet zu, um größere Sätze von Wörtern zu finden. Ich fand sehr große Wortgruppen, die riesig waren, aber als ich anfing, nach perfekten Pangrams aus diesen Listen zu suchen, stellte ich fest, dass sie viel zu stark mit Wörtern von geringer Qualität verschmutzt waren, die keine gültigen englischen Wörter sind. Selbst nach vielen Iterationsrunden konnte ich die Liste nicht durchgehen, um vernünftige oder überschaubare Pangrams zu finden. Ich habe versucht, es zu bereinigen, indem ich eine Whitelist mit Wörtern bestimmter Länge erstellt habe, aber die Liste war immer noch von extrem geringer Qualität.

Schließlich zahlte ich nach vielen Iterationen 15 US-Dollar, um eine Probemitgliedschaft für Nordamerika zu kaufen Scrabble® Players Association, die mir Zugang zu dem geschützten und urheberrechtlich geschützten OWL3 verschaffte, das einige Kontroversen auslöst. Selbst dann musste ich einige bekannte englische Wörter hinzufügen, wie zum Beispiel die Einzelbuchstaben „a“ und „I“.

Ausgerüstet mit einer richtigen Liste von Wörtern implementierte ich einen Algorithmus zum Produzieren Alle Sätze von Wörtern aus dieser Liste, die jeweils einen Buchstaben des englischen Alphabets enthalten. Ich werde den Algorithmus im folgenden Abschnitt „Der Algorithmus“ ausführlich beschreiben.

Schritt 2: Bilden englischer Sätze aus einer Worttasche

Bei einer Reihe von Wörtern muss herausgefunden werden, ob a Ein gültiger englischer Satz ist mit allen bereitgestellten Wörtern möglich. Dies ist ein nicht triviales Problem, aber einfacher als die meisten anderen Probleme bei der Verarbeitung natürlicher Sprache (NLP).

Es gibt nützliche Heuristiken, um nicht förderfähige Sätze auszusortieren. Nachdem ich diesen Heuristiken gefolgt war, konnte ich aus den verbleibenden Wörtern gültige englische Sätze bilden. Die Sätze waren oft unsinnig, aber immer noch gültig. Hier sind die Heuristiken, die ich verwendet habe:

1. Es muss mindestens ein Verb geben.
2. Es kann nur ein Substantiv mehr geben als Verben, es sei denn, es gibt eine Konjunktion oder eine Präposition, die beide sehr selten sind.
3. Wenn es Adjektive gibt, müssen auch Substantive vorhanden sein.

Die Heuristik funktioniert teilweise aufgrund der Möglichkeit der Implikation Themen (weder perfekt noch ein Pangram, sondern „leise bewegen und leise sprechen“ ist ein Satz mit zwei Verben und keinen Substantiven, mit dem impliziten Thema „du“).

Da der Raum der Wörter, die können Möglicherweise ist die Teilnahme an perfekten Pangrams klein. Es ist einfach genug, jedes einzelne Wort manuell mit seinen geeigneten Wortarten zu versehen und zu prüfen, ob die Wortgruppe diesen drei einfachen Heuristiken entspricht. Ob Ihnen die Qualität der produzierten Sätze gefällt oder nicht, ist Geschmackssache.

Der Algorithmus

Dieser Abschnitt ist ein bisschen technisch, aber hoffentlich immer noch leicht zu befolgen. Fahren Sie mit dem Abschnitt „Ergebnisse & Learnings“ fort.

Strategie auf hoher Ebene

Ziel ist es, alle möglichen Sätze von zu erstellen Wörter aus der angegebenen Liste von Wörtern, die das englische Alphabet „perfekt“ überspannen.

1. Bereinigen Sie die Liste der Wörter, um den Suchraum drastisch zu reduzieren, z Entfernen Sie Wörter mit wiederholten Buchstaben, z. B. „Buchstaben“.
2. Verwenden Sie Bitmasken, um Wörter effizient darzustellen, und ordnen Sie sie den ursprünglichen Wortgruppen zu.
3. Durchsuchen Sie alle möglichen Zustände. Jedes stellt eine mögliche Buchstabenkombination dar, indem die Liste der Bitmasken wiederholt durchlaufen wird. Die Leistung wird durch dynamische Programmierung erheblich verbessert.
4. Zeichnen Sie Pfeile (gerichtete Kanten) aus dem perfekten Pangram-Zustand, dem Endzustand, der alles enthält die englischen Buchstaben an die Zwischenzustände, aus denen es besteht. Wiederholen Sie dies mit den Zwischenzuständen, um eine Datenstruktur zu erstellen, die die Sätze von Wörtern rekonstruieren kann, die möglicherweise perfekte Pangrams sind. Dies wird als Backtracking bezeichnet.
5. Ausgabe die entdeckten Sätze von Wörtern, die möglicherweise perfekte Pangrams als Bäume sind.

Bereinigen der Liste, auch bekannt als Canonicalization

Der erste Schritt besteht darin, die ursprüngliche Wortliste zu bereinigen, um den Suchraum zu verringern und die Ausgabequalität zu erhöhen.

1. Entfernen Sie alle Leerzeichen um das Wort und konvertieren Sie es nur in Kleinbuchstaben
2. Stellen Sie sicher, dass die Wörter nur Buchstaben des englischen Alphabets enthalten. Ich habe einen einfachen Filter für reguläre Ausdrücke verwendet: /^+$/
3. Filter gegen andere Listen, z. schwarze Listen; Wenn sich ein Wort in der schwarzen Liste befindet, überspringen Sie dieses Wort.
4. Entfernen Sie alle Wörter mit wiederholten Buchstaben.

Dadurch wurde der Suchraum von Listen mit 200.000 bis 370.000 Wörtern erheblich verkürzt viel kleinere 35.000 ~ 65.000 Wörter.

Verwenden von Bitmasken

Bitmasken sind ganzzahlige Darstellungen von Zuständen. Bitmasken bieten mehrere Vorteile:

• Bitmasken repräsentieren dieses Problem gut. Die Reihenfolge der Buchstaben spielt keine Rolle, daher können alle Wortkombinationen als 26-stellige Reihe von Nullen und Einsen dargestellt werden, wobei jede Ziffer angibt, ob ein Buchstabe in der Kombination vorhanden ist oder nicht. Zum Beispiel. Wenn der Satz von Wörtern den Buchstaben „e“ enthält, ist die 5. Ziffer eine 1, andernfalls eine 0.
• Bitmasken sind effizient: Da der Suchraum konstant ist, bieten Bitmasken eine effiziente Speicherung und Darstellung aller möglichen Buchstabenkombinationen. Darüber hinaus sind bitweise Operationen schnell. Um zu testen, ob zwei Bitmasken zu einer größeren Bitmaske kombiniert werden können, prüfen Sie, ob das bitweise UND der beiden Masken gleich 0 ist. Beide sind extrem schnelle Operationen.

Verwandeln Sie also jedes Wort in eine Bitmaske, die als Ganzzahl dargestellt werden kann. Beispielsweise wird das Wort „cab“ auf die Bitmaske von 111 abgebildet, die ist die Dezimalzahl 7. Das Wort „be“ wird auf 10010 abgebildet, was die Dezimalzahl 18 usw. ist. Die größtmögliche Bitmaske ist eine mit allen Buchstaben des Alphabets, dem möglichen perfekten Pangram-Zustand, 111111111111111111111111, Dies ist die Dezimalzahl 67.108.863 oder 2²⁶ -1. Dies passt gut zu einer standardmäßigen vorzeichenbehafteten 32-Bit-Ganzzahl, die bis darstellen kann bis 2³¹-1.

Durch die Verwendung von Bitmasken wird der Platz weiter komprimiert, da Einzelwortanagramme derselben Bitmaske zugeordnet werden. Sowohl „Ofen“ als auch „Link“ werden der Maske 10110100000000 zugeordnet, bei der es sich um die Dezimalzahl 11520 handelt. Dadurch wird der Suchraum von 35.000 bis 65.000 Wörtern weiter auf 25.000 bis 45.000 Bitmasken reduziert.

Behalten Sie eine Zuordnung der Bitmaske zu den Wörtern bei, von denen sie abgeleitet sind. Dies ist nützlich, wenn Sie die Wortgruppen ausgeben.

Suchen nach dem perfekten Pangram mit dynamischer Programmierung

Der Kern des Algorithmus ist ziemlich einfach:

Versuchen Sie bei einem möglichen Status (der sich aus gültigen Kombinationen vorhandener Wörter zusammensetzt) alle Masken aus der anfänglichen Wortliste, um festzustellen, ob es möglich ist, einen neuen gültigen Status zu erstellen (indem Sie überprüfen, ob das bitweise UND von Der Zustand und die Maske sind gleich 0, was bedeuten würde, dass es keine überlappenden Buchstaben gibt. Erstellen Sie den neuen Status mithilfe der bitweisen ODER-Verknüpfung, bei der alle Einsen zusammengeführt werden. Wiederholen Sie diesen Vorgang für jeden neu entdeckten Zustand so lange, bis keine unerforschten Zustände mehr vorhanden sind. Wenn dies das Ende erreicht, bedeutet dies, dass der Algorithmus mindestens einen möglichen perfekten Pangram-Wortsatz gefunden hat. Der erste mögliche Zustand, der alle möglichen Zustände auflisten kann, ist der leere Zustand oder 0, in dem keine Buchstaben des Alphabets enthalten sind. Beginnen Sie also dort und entdecken Sie dann rekursiv, welche Zustände möglich sind.

Ein großer Effizienzgewinn besteht darin, zu bemerken, dass es viele Möglichkeiten gibt, einen intermittierenden Zustand zu erreichen, und dass sich die Arbeit am Zustand nicht basierend darauf ändert wurde erreicht. Speichern Sie also das Ergebnis jedes Status, anstatt die Arbeit zu wiederholen, wenn ein Status erneut aufgerufen wird. Diese Technik wird als dynamische Programmierung bezeichnet und verwandelt ein komplexes kombinatorisches Problem in ein lineares Programm. Das Speichern des intermittierenden Zustands wird als Memoisierung bezeichnet.

Erstellen Sie also ein Array der Größe 2²⁶ zwischen 0 und 67.108.863 einschließlich. Jeder Index repräsentiert einen Bitmaskenzustand, wie zuvor erläutert. Der Wert an jedem Index des Arrays gibt an, was über den Status bekannt ist. 0 bedeutet entweder, dass der Status unberührt oder nicht erreichbar ist. 1 bedeutet, dass der Staat einen Weg gefunden hat, um den möglichen perfekten Pangram-Zustand zu erreichen. -1 bedeutet, dass der Status keinen Weg gefunden hat, das Ende zu erreichen.

Pseudocode unten:

Zwischenspiel: Komplexität und praktische Laufzeitanalyse

Es gibt 2²⁶ mögliche Bitmasken für eine Reihe von 26 Bits. Da jeder Zustand aufgrund von Memoisierung nur einmal verarbeitet wird, ist die Laufzeit dieses Algorithmus O (n 2 ^ d), wobei d die Größe des Alphabets 26 ist. Die Variable n steht nicht für die Anzahl der Wörter, sondern für die Anzahl der Bitmasken. Mit 67.108.863 und ungefähr 45.000 Bit-Masken liegt dies in der Größenordnung von 3 Billionen, die mein MacBook Pro in ungefähr 45 Minuten verarbeiten könnte. Für jeden modernen Computer handhabbar. Es ist auch erwähnenswert, dass der rekursive Aufrufstapel niemals tiefer als 26 wird (wahrscheinlich niemals tiefer als 15), so dass er auch in dieser Dimension sehr gut handhabbar ist.

Ein Vorteil des Bitmaskenansatzes mit Nur 2²⁶-Zustände bedeuten, dass alle Zustände im Speicher gespeichert werden können. Da es nur 3 Werte pro Zustand gibt (-1, 0, 1), kann dies in einem einzelnen Byte gespeichert werden. Bei einem einzelnen Byte pro Status ergeben 2²⁶-Status ungefähr 67 Megabyte, was wiederum sehr überschaubar ist.

Mit zunehmendem Alphabet nimmt der Suchraum jedoch exponentiell zu, ebenso wie die Laufzeit, wodurch die Problem, sehr schnell unlösbar zu werden. Eine kurze Diskussion über die Annäherung an das perfekte Pangram für größere Alphabete finden Sie im Abschnitt „Sprache mit größeren Alphabeten“ weiter unten.

Dynamisches Erstellen eines gerichteten azyklischen Graphen (DAG)

Nun, da wir haben die Bitmaskenzustände ausgefüllt, Zeit, um die Lösung abzurufen!

Um die Sätze von Wörtern zu finden, die den Satz möglicher perfekter Pangrams erzeugt haben, müssen wir ableiten, welche Zwischenzustände für die Zusammenstellung der Endzustände wesentlich waren Die folgende Frage lautet dann, welche anderen Zwischenzustände diese Zwischenzustände zusammengesetzt haben, und so weiter, bis nur noch die Zustände übrig sind, die direkt auf Wörter abgebildet werden. Dieser Vorgang wird als Backtracking bezeichnet.

Beibehalten Verfolgung der Beziehungen zwischen Staaten, das Ziel ist es, eine Di zu erstellen Acyclical Graph (DAG), der angibt, welche Zwischenzustände einen bestimmten Zustand bilden. DAGs sind leicht zu durchlaufen, um Ausgaben abzurufen, insbesondere aufgrund ihrer nichtzyklischen Natur. Beginnen Sie zum Konstruieren mit dem möglichen perfekten Pangram-Zustand und erstellen Sie eine gerichtete Kante (Pfeil), die auf die Zwischenzustände zeigt, aus denen er besteht. Wiederholen Sie den Vorgang mit den Zwischenzuständen, und es wird eine DAG erstellt. Es wird niemals Zyklen geben, da die Pfeile immer auf einen Zustand mit einem kleineren Wert zeigen.

Anstatt die im Suchschritt entdeckten Beziehungen wiederherzustellen, bei denen Billionen möglicher Statuskombinationen erneut durchlaufen werden, ist es effizienter, die DAG während der dynamischen Programmierphase zu erstellen. Wenn innerhalb der Lösungsmethode ein neu konstruierter Zustand den möglichen perfekten Pangram-Zustand erreichen kann, speichern Sie eine gerichtete Kante vom neu konstruierten Zustand in den ursprünglichen Zustand nur dann, wenn der ursprüngliche Zustand kleiner als sein Komplement ist (um die Kantenverdoppelung zu verringern).

Drucken Sie die Früchte Ihrer Arbeit in Baumform aus!

Das wahrscheinlich einfachste Format zum Anzeigen der resultierenden Wortgruppen besteht darin, sie als Bäume mit dem Wurzelknoten als perfektem Pangram-Status aufzulisten. Angesichts der von oben aufgebauten DAG besteht der beste Weg zum Entpacken darin, dies rekursiv zu tun und jeden Zustand bei jedem Schritt auf die Festplatte zu schreiben, anstatt im Speicher, da der Baum eine Größenordnung größer als die DAG ist.

Eine Verbesserung dieser Form der Erweiterung besteht darin, Zustände zusammenzufassen, die nur eine einzige mögliche Kombination von Wörtern haben. Ein Zustand, der eine Maske für Wörter und keine Unterzustände ist, aus denen er besteht, kann trivial zusammengefasst werden. Ein Zustand kann zusammengefasst werden, wenn seine Unterzustände und seine Verbundstoffe zusammengefasst werden können und alle von sich selbst und seinen untergeordneten Masken abgeleiteten Masken keine überlappenden Bits / Zeichen aufweisen. Das Drucken der zusammengefassten DAG verbessert die Lesbarkeit des resultierenden Ausgabebaums durch Verkürzen und Vereinfachen.

Da die Zusammenfassung nur vom kleineren der beiden Zustände abhängt, wird das Array vom Anfangszustand 0 aufwärts und durchlaufen Wenn Sie die oben genannten Regeln verwenden, um die Zusammenfassungsregel zu verwalten, kann dies in linearer Zeit abgeschlossen werden.

Produzierte Pangram-Bäume!

Sie können jederzeit die perfekten Pangram-Bäume durchlaufen, um zu sehen, ob Sie dies tun kann interessante Sätze finden!

Es gibt viele mögliche perfekte Pangrams

Ich war überrascht von der Anzahl der perfekt möglichen Pangrams. Es gibt eine Menge! Die beste Strategie, um sie zusammenzusetzen, erfordert keinen komplexen Prozessor für natürliche Sprache. Sobald die Kandidatenwörter als Nomen oder Verb geeignet gekennzeichnet wurden, muss der Wortbeutel mindestens ein Nomen, ein Verb und das richtige Verhältnis von Nomen und Verben enthalten.

Datenqualität ist ein schwieriges Problem

Der Algorithmusabschnitt dauerte zwei Tage, das Datenqualitätsproblem jedoch zwei Wochen. Als ich meinem Freund, einem leitenden Ingenieur bei Google, von dieser Erkenntnis erzählte, war er nicht überrascht und bemerkte, dass Datenqualitätsprobleme zu den schwierigsten Problemen im Engineering gehören. Lektion gelernt.

Die Regeln perfekter Pangrams

Es gibt viele Nuancen, was sich als perfektes Pangram qualifiziert! Ich wollte Pangrams ohne Interjektionen durchsuchen (z. B. hm, pht), aber es gibt auch andere populäre Einschränkungen wie Abkürzungen, Akronyme, Kontraktionen, Initialismen, isolierte Buchstaben, Eigennamen und römische Ziffern. Es gibt auch Wörter, die Namen von Buchstaben sind, wie Qoph, von dem ich dachte, dass er betrügt.

Wenn einige dieser Einschränkungen gelockert sind, gibt es viele „perfekte“ Pangrams. Wahrscheinlich in der Größenordnung von Billionen Es gibt viele Akronyme und Initialismen.

Das Sternchen

Das Sternchen ist vorhanden, weil die Definition aller perfekten Pangrams des Englischen nicht genau definiert ist. Es gibt Nuancen Bezogen auf das, was in perfekten Pangrams des Englischen erlaubt sein sollte. Es gibt auch viele Streitigkeiten darüber, ob einige Wörter überhaupt englische Wörter sind oder nicht. Angesichts dieser Nuancen ist es wirklich schwierig zu sagen, dass ich alle perfekten Pangrams gefunden habe. Ich kann zwei Behauptungen ziemlich sicher aufstellen:

1. Ich habe eine Methode gefunden, um alle perfekten Pangrams von Englisch und anderen Sprachen mit ähnlichen oder kleineren Zeichensätzen zu erzeugen.
2. I. haben alle Sätze von Wörtern aufgelistet, die möglicherweise perfekte Pangrams bilden können, indem sie das offizielle Scrabble-Turnierwörterbuch verwenden y, OWL3.

Bitte zögern Sie nicht, Ihre eigenen perfekten Pangrams mit den in diesem Beitrag beschriebenen Techniken zu produzieren!

Die Abhängigkeit von Perfect Pangrams von Wörtern walisischer und arabischer Wurzeln

Von Walisisch und Arabisch abgeleitete Wörter waren wirklich wichtig für die Existenz perfekter englischer Pangrams (es sei denn, die Einschränkungen des perfekten Pangrams werden gelockert). Unter Verwendung der OWL3-Wortliste mit strengen Regeln für perfekte Pangrams gibt es keine perfekten Pangrams, die nicht die Wörter „cwm (s)“ oder „crwth (s)“ enthalten, beides walisische Wörter. In International Scrabble ist das arabisch abgeleitete Wort „waqf (s)“ ein gültiges Wort, das perfekte Pangrams erzeugen kann, ohne auf „cwm (s)“ oder „crwth (s)“ zurückzugreifen.

Effizienz des Arbeitsstroms

Es war wichtig, die Parallelisierung von Aufgaben während dieses Projekts effizienter zu gestalten. Ein vollständiger Lauf dauert 25 Minuten für das Unix-Wörterbuch und fast eine Stunde für die wirklich großen Wörterbücher. Ich hatte einige anfängliche Probleme beim Kontextwechsel für ein 30-minütiges Fenster, wurde aber im Laufe der Zeit besser, um meine Produktivität zu verbessern.

Erweiterung / Generalisierung – Anagram Finder

Das perfekte Pangram Die Suche entspricht auch einem Anagrammfinder für die Zeichenfolge „abcdefghijklmnopqrstuvwxyz“. Was ist, wenn Sie einen generischen Anagrammfinder erstellen möchten?

Dieselbe Technik kann verwendet werden, solange die Zustandsdarstellung und die Verwaltungsregeln für die Überprüfung gelten Die Gültigkeit von Wortkombinationen wird aktualisiert. Anstatt Zustände als Ganzzahl zu verwalten, ist es einfacher, den Zustand als Karte der relevanten Zeichen zu verfolgen. Wenn Sie prüfen, ob Kombinationen gültig sind, bedeutet dies, dass die Kombination zweier Karten die nicht überschreitet Stellen Sie sicher, dass der Statusraum nachvollziehbar ist. Bei zu vielen Buchstaben kann der Suchraum im Handumdrehen sehr groß werden. Dürfen Sie auch Wörter wiederholen? Stellen Sie sicher, dass Sie diese Regeln darin definieren Ihre dynamische Programmierung Lösung.

Sprachen mit größeren Alphabeten

Dieser Ansatz und diese Lösung sind in der Größe des Wortsatzes linear, in der Alphabetgröße jedoch exponentiell. Dieser Ansatz funktioniert möglicherweise nicht mit einem größeren Zeichensatz, beispielsweise dem modernen Japanisch mit 46 Silben. 2⁴⁶ ist 70.368.744.177.664; mehr als eine Million Mal größer als der englische Suchraum von 2²⁶ = 67.108.864.

Es ist nicht ganz klar, ob dieser Ansatz für Japanisch funktionieren würde oder nicht. Wenn die japanische Sprache eine ausreichend niedrige Entropie aufweist, was möglich ist, wäre dieser Ansatz praktikabel. Anstatt ein Array der Größe 2⁴⁶ zu initialisieren, werden die Zustände in einer Karte verfolgt. Darüber hinaus kann die Struktur des Japanischen ausgenutzt werden; Zum Beispiel wird das Kana を (wo) fast ausschließlich als Post-Positions-Partizip verwendet und kann von der Suche ausgeschlossen werden, wodurch der Suchraum verringert wird.

Die kambodschanische Sprache der Khmer hat mit 74 das größte Alphabet. Ein weiterer möglicher nächster Schritt besteht darin, Lösungen zu untersuchen, deren Alphabetgröße subexponentiell ist.

Inspiration

Ich wurde von Aubrey De Greys Fortschritt bei der Suche nach der chromatischen Zahl der Ebene inspiriert mindestens 5. Dies ist ein bedeutender Fortschritt, der durch grundlegende Berechnungsmethoden erreicht wurde.

Es ist unnötig zu erwähnen, dass das Finden perfekter Pangrams keine Kerze für die Verbesserung der Untergrenze der chromatischen Zahl einer Ebene darstellt.

Dies lässt mich glauben, dass es viele Probleme mit niedrig hängenden Früchten gibt, die einfache Berechnungsmethoden zur Lösung eines Problems haben, das manuell nicht zu lösen ist. Ich fordere Sie auf, einige dieser Probleme zu finden und zu lösen. Bitte lassen Sie mich wissen, wenn Sie etwas finden!

Danke

Ich bin sehr dankbar für meine hervorragenden Freunde, die mir beim Korrekturlesen und Jammen geholfen haben, insbesondere bei Anna Zeng, Catherine Gao, Danny Wasserman, George Washington und Nick Wu!