Angenommen, Sie hatten eine Tüte mit Kacheln, auf denen sich jeweils ein Buchstabe befindet. Es gibt Kacheln mit dem Buchstaben 'A', mit 'B' usw. und 'Wildcard'-Kacheln (wir haben ). Angenommen, Sie hätten ein Wörterbuch mit einer begrenzten Anzahl von Wörtern.n A n B n ∗ n = n A + n B + … + n Z + n ∗
Sie wählen Fliesen aus dem Beutel ohne Ersatz.
Wie würden Sie die Wahrscheinlichkeit berechnen (oder schätzen), mit der Sie ein bestimmtes Wort der Länge (mit 1 < = < ) aus dem Wörterbuch bilden können, wenn Sie die ausgewählten Kacheln verwenden?l k k
Für diejenigen, die mit Scrabble (TM) nicht vertraut sind, kann das Platzhalterzeichen für jeden Buchstaben verwendet werden. So könnte das Wort "BOOT" mit den Kacheln "B", "*", "O", "T" "geschrieben" werden. Die Reihenfolge, in der die Buchstaben gezeichnet werden, spielt keine Rolle.
Vorschlag: Um das Schreiben von Antworten zu vereinfachen, ist es möglicherweise besser, nur die Frage zu beantworten: Wie hoch ist die Wahrscheinlichkeit, dass das Wort "BOOT" zu Ihren möglichen Zügen gehört, nachdem Sie 7 Buchstaben aus einem neuen Beutel gezogen haben.
(Die Einführung des Problems wurde von dieser ähnlichen Frage kopiert. )
quelle
Antworten:
Eine Formel wird angefordert. Leider ist die Situation so kompliziert, dass es den Anschein hat, dass jede Formel nur ein Umweg ist, um alle Möglichkeiten aufzuzählen. Stattdessen bietet diese Antwort einen Algorithmus, der (a) einer Formel entspricht, die Produktsummen von Binomialkoeffizienten enthält, und (b) auf viele Plattformen portiert werden kann.
Um eine solche Formel zu erhalten, teilen Sie die Möglichkeiten auf zwei Arten in voneinander getrennte Gruppen auf: Je nachdem, wie viele Buchstaben nicht im Wort im Rack ausgewählt sind (sei dies ) und wie viele Platzhalter (Leerzeichen) ausgewählt sind ( lass das sein w ). Wenn sie r = 7 Kacheln in dem Gestell, N verfügbar Fliesen, M verfügbar Fliesen mit Buchstaben nicht in dem Wort, und W = 2 Zuschnitten verfügbar, da die Anzahl der möglichen Auswahl von ( m , w ) ist ,m w r=7 N M W=2 (m,w)
weil die Auswahl von Nicht-Wort-Buchstaben, Leerzeichen und Wort-Buchstaben unabhängig von(m,w,r).
Dies verringert das Problem, die Anzahl der Möglichkeiten zu finden, ein Wort zu buchstabieren, wenn nur aus den Kacheln ausgewählt wird, die die Buchstaben des Wortes darstellen, vorausgesetzt , Leerzeichen sind verfügbar und r - m - w Kacheln werden ausgewählt. Die Situation ist chaotisch und es scheint keine geschlossene Formel verfügbar zu sein. Zum Beispiel werden mit w = 0 Leerzeichen und m = 3 ausstehenden Buchstaben genau vier Buchstaben übrig bleiben, um "boot" zu buchstabieren, die aus den Kacheln "b", "o" und "t" gezogen wurden . Vorausgesetzt, es gibt 2 "b" 's, 8 "o"' s und 6w r−m−w w=0 m=3 2 8 6 "t" im Scrabble-Kachelsatz gibt es positive Wahrscheinlichkeiten für das Zeichnen (Multisets) "bboo", "bbot", "bbtt", "booo", "boot", "bott", "bttt", "oooo" "," ooot "," oott "," ottt "und" tttt ", aber nur einer dieser Zauber" booten ". Und das war der einfache Fall! Angenommen, das Rack enthält fünf Kacheln, die nach dem Zufallsprinzip aus den Kacheln "o", "b" und "t" ausgewählt wurden. Zusammen mit beiden Leerzeichen gibt es viele weitere Möglichkeiten, "boot" zu buchstabieren - und nicht, es zu buchstabieren. Zum Beispiel kann "boot" von "__boott" und "__bbttt" geschrieben werden, aber nicht von "__ttttt".
Diese Zählung - das Herzstück des Problems - kann rekursiv behandelt werden. Ich werde es mit einem Beispiel beschreiben. Angenommen, wir möchten die Schreibweisen für "boot" mit einem Leerzeichen und vier weiteren Kacheln aus der Sammlung der Kacheln "b", "o" und "t" zählen (daher werden auf den verbleibenden beiden Kacheln nicht leere Buchstaben angezeigt, die nicht in {enthalten sind. "b", "o", "t"}). Betrachten Sie den ersten Buchstaben "b":
A "b" kann eingezogen werden Wege von den beiden verfügbaren "b" -Kacheln. Dies reduziert das Problem, die Anzahl der Schreibweisen für das Suffix "oot" unter Verwendung beider Leerzeichen und nur drei weiterer Kacheln aus der Sammlung von "o" - und "t" -Kacheln zu zählen.(21)
Ein Leerzeichen kann als "b" bezeichnet werden. Dies reduziert das Problem, die Anzahl der Schreibweisen "oot" unter Verwendung des verbleibenden Leerzeichens und nur drei weiterer Kacheln aus der Sammlung von "o" - und "t" -Kacheln zu zählen.
Im Allgemeinen können die Schritte (1) und (2) - die disjunkt sind und daher zusätzlich zu den Wahrscheinlichkeitsberechnungen beitragen - als Schleife über die mögliche Anzahl von Leerzeichen implementiert werden, die für den ersten Buchstaben verwendet werden können. Das reduzierte Problem wird rekursiv gelöst. Der Basisfall tritt auf, wenn nur noch ein Buchstabe übrig ist, eine bestimmte Anzahl von Kacheln mit diesem Buchstaben verfügbar ist und möglicherweise auch einige Leerzeichen im Rack vorhanden sind. Wir müssen nur sicherstellen, dass die Anzahl der Rohlinge im Rack plus die Anzahl der verfügbaren Kacheln ausreicht, um die gewünschte Menge des letzten Buchstabens zu erhalten.
Hier ist7
R
Code für den rekursiven Schritt.rack
in der Regel gleich , ist eine Reihe von Anzahlen der Buchstaben (wie z. B. ), ist eine ähnliche Struktur, die die Anzahl der verfügbaren Kacheln mit diesen Buchstaben angibt, und ist die Anzahl der Leerzeichen, von denen angenommen wird, dass sie im Rack vorkommen.word
c(b=1, o=2, t=1)
alphabet
wild
Eine Schnittstelle zu dieser Funktion spezifiziert die Standard-Scrabble-Kacheln, konvertiert ein gegebenes Wort in seine Multiset-Datenstruktur und führt die Doppelsumme über und w aus . Hier sind die Binomialkoeffizienten ( Mm w und ( W(Mm) werden berechnet und multipliziert.(Ww)
Probieren wir diese Lösung aus und nehmen uns die Zeit dafür. Der folgende Test verwendet dieselben Eingaben, die in den Simulationen von @Rasmus Bååth verwendet wurden :
Dieses Gerät meldet eine Gesamtzeit von Sekunden: ziemlich schnell. Die Ergebnisse?0.05
Die Wahrscheinlichkeit für „boot“ von entspricht genau den Wert 2381831 / 333490850 in erhielt meine andere Antwort (die ein ähnliches Verfahren verwendet , aber die Liegen sie in einem leistungsfähigeren Rahmen eine symbolische Algebra Computing - Plattform erfordert). Die Wahrscheinlichkeiten für alle vier Worte sind ziemlich nahe an Bååth der Simulationen (was erwartet werden konnte keine genauen Wert für „Zoologie“ wegen seiner geringen Wahrscheinlichkeit geben 11840 / 16007560800 , das weniger als eins zu einer Million).114327888/16007560800 2381831/333490850 11840/16007560800,
quelle
R
aber dennoch geschafft, Ihre Funktionen in weniger als einer Stunde zu nutzen, sodass das Skript Eingaben aus einer Wörterbuchdatei mit 20.000 Wörtern entgegennimmt und Ergebnisse in eine CSV-Datei schreibt. (Dies dauerte weniger als 10 Minuten auf einem Mittelklasse-Core i5)Die Antworten auf die Frage , auf die verwiesen wird, gelten hier direkt: Erstellen Sie ein Wörterbuch, das nur aus dem Zielwort (und seinen möglichen Platzhaltern) besteht, berechnen Sie die Wahrscheinlichkeit, dass ein zufälliges Rack das Ziel nicht bilden kann, und subtrahieren Sie diese von . Diese Berechnung ist schnell.1
Simulationen (am Ende gezeigt) unterstützen die berechneten Antworten.
Einzelheiten
Wie in der vorherigen Antwort wird Mathematica verwendet, um die Berechnungen durchzuführen.
Geben Sie das Problem an: das Wort (oder die Wörter, wenn Sie möchten), die Buchstaben, deren Anzahl und die Rackgröße. Da alle Buchstaben nicht in dem Wort das gleiche handeln, es beschleunigt erheblich die Berechnung sie alle durch ein einzelnes Symbol zu ersetzen darstellt „jeden Buchstaben nicht im Wort.“χ
Erstellen Sie ein Wörterbuch dieses Wortes (oder dieser Wörter) und erweitern Sie es, um alle möglichen Platzhalter-Schreibweisen einzuschließen.
Berechnen Sie die Nichtwörter:
Berechnen Sie die Chancen. Ersetzen Sie für Stichproben mit Ersetzung einfach die Anzahl der Kacheln durch die Variablen:
Verwenden Sie für die ersatzlose Abtastung Fakultätskräfte anstelle von Kräften:
Simulationsergebnisse
Vergleichen Sie es mit dem berechneten Wert relativ zu seinem Standardfehler:
Die Vereinbarung ist in Ordnung und stützt das berechnete Ergebnis nachdrücklich.
Machen Sie den Vergleich:
Die Übereinstimmung in dieser Simulation war ausgezeichnet.
quelle
Das ist also eine Monte-Carlo- Lösung, das heißt, wir werden das Zeichnen der Kacheln millionenfach simulieren und dann berechnen, wie viele dieser simulierten Zeichnungen dazu geführt haben, dass wir das gegebene Wort bilden konnten. Ich habe die Lösung in R geschrieben, aber Sie können jede andere Programmiersprache verwenden, z. B. Python oder Ruby.
Ich werde zuerst beschreiben, wie man eine Ziehung simuliert. Definieren wir zunächst die Kachelfrequenzen.
Codiere dann das Wort als einen Vektor der Buchstabenanzahl.
Zeichnen Sie nun ein Muster von sieben Kacheln und kodieren Sie sie wie das Wort.
Berechnen Sie endlich, welche Buchstaben fehlen ...
... und addiere die Anzahl der fehlenden Buchstaben und subtrahiere die Anzahl der verfügbaren Leerzeichen. Wenn das Ergebnis Null oder weniger ist, ist es uns gelungen, das Wort zu buchstabieren.
In diesem speziellen Fall haben wir es jedoch nicht getan ... Jetzt müssen wir dies nur noch viele Male wiederholen und den Prozentsatz der erfolgreichen Ziehungen berechnen. All dies erledigt die folgende R-Funktion:
Hier
reps
ist die Anzahl der simulierten Ziehungen. Jetzt können wir verschiedene Wörter ausprobieren.quelle
sample
verhält sich nicht so, wie Sie es zu erwarten scheinen. Was passiert zum Beispiel mit Ihrem Code, wenn das Spiel so geändert wird, dass ein Rack mit 28 Steinen zulässig ist? Wechseln Siesize=7
zusize=28
, um dies herauszufinden.Für das Wort "BOOT" ohne Platzhalter:
quelle
Meh.
Es ist schon eine Weile her, dass ich mir angesehen habe, wie ich mein Projekt aufgebaut habe. Und meine Mathematik ist möglicherweise ganz falsch oder richtig. Ich kann es rückwärts haben. Ehrlich gesagt, ich vergesse. ABER! Verwenden Sie nur eine Binomialkombination, ohne leere Kacheln zu berücksichtigen, die das Ganze aus dem Gleichgewicht bringen. Die einfache Kombinationslösung ohne Wild.
Ich habe mir diese Fragen selbst gestellt und deshalb mein eigenes Wörterbuch für Scrabble-Wörter-Wahrscheinlichkeiten erstellt . Sie brauchen kein Wörterbuch mit möglichen Wörtern, sondern nur die Mathematik dahinter und verfügbare Buchstaben, die auf den Buchstaben in der Fliesentasche basieren. Die Reihe der englischen Regeln finden Sie weiter unten. Ich habe Wochen damit verbracht, die Mathematik zu entwickeln, um diese Frage für alle englischen Wörter zu beantworten, die in einem Spiel verwendet werden können, einschließlich Wörter, die in einem Spiel nicht verwendet werden können. Es kann alles falsch sein.
Die Wahrscheinlichkeit, in Scrabble ein bestimmtes Wort aus einer Buchstabenkiste zu ziehen, hängt davon ab, wie viele Buchstaben in der Buchstabenkiste für jeden Buchstaben (AZ) verfügbar sind und ob wir den Platzhalter als Ergänzung zur Mathematik verwenden. Die leeren Kacheln sind in dieser Berechnung enthalten - vorausgesetzt, 100 Kacheln, von denen 2 leer sind. Außerdem hängt die Anzahl der verfügbaren Kacheln von der jeweiligen Spielsprache und den Spielregeln auf der ganzen Welt ab. Englisches Scrabble unterscheidet sich offensichtlich von arabischem Scrabble. Ändern Sie einfach die verfügbaren Buchstaben, und die Mathematik sollte die Arbeit erledigen.
Wenn jemand Fehler findet, werde ich sie auf jeden Fall aktualisieren und beheben.
Boot : Die Wahrscheinlichkeit von Boot in einem Scrabble-Spiel beträgt 0,000386%, was einer Chance von 67 aus 173,758 Händen entspricht, wie auf der Wortseite für Boot angegeben .
Englische Fliesen
Alles ist die Anordnung der Buchstaben in der Tasche. count ist das Array der verfügbaren Kacheln für diesen Buchstaben und point ist der Punktwert des Buchstabens.
Es gibt 100 Steine in einem englischen Scrabble-Spiel (dh die Summe von
$count
). Es spielt keine Rolle, wie die Kacheln gezogen werden, es ist also keine Permutation.Die verwendete Mathematik Bestimmen Sie, wie viele Buchstaben das Wort enthält und welche Buchstaben es enthält, wie viele dieser Buchstaben in der Kacheltasche vorhanden sind (Anzahl für jeden Buchstaben, jedes Unikat und jedes Allchar). Binomialkoeffizient von jedem, dividiert durch den Binomialkoeffizienten des Längenworts.
Bestimmen Sie die verfügbaren Binomialkombinationen
Für jeden Buchstaben, was ist der Binomialkoeffizient.
Es gibt 1 "B". Es stehen 2 zur Verfügung, eine 2% ige Chance, die b zu ziehen.
Es gibt 2 "O". Es sind 8 verfügbar, eine Chance von 8%, das o zu ziehen.
Es gibt 1 "T". Es sind 6 verfügbar, eine Chance von 6%, das t zu ziehen.
BOOT ist ein 4-Buchstaben-Wort, das aus einem 100er-Kachelsatz mit Leerzeichen stammt, 98 ohne.
n = 98. Die Anzahl der Kacheln ohne Leerzeichen im englischen Satz
quelle
R
mir geposteten Lösung erhalten. Versuchen Sie diese einsekündigeR
Simulation:let <- c(rep("b", 2), rep("o", 8), rep("t", 6), rep("_", 84)); boot <- function(x) sum(x=="b")>=1 && sum(x=="o")>=2 && sum(x=="t")>=1; mean(replicate(1e5, boot(sample(let, 7))))