Wahrscheinlichkeit, dass in Scrabble kein Wort aus einer Buchstabentüte gezogen wird

Angenommen, Sie hatten eine Tüte mit Kacheln, auf denen jeweils ein Buchstabe stand. Es gibt n A- Kacheln mit dem Buchstaben 'A', n B mit 'B' usw. und n ∗ 'Platzhalter'-Kacheln (wir haben n = n A + n B + ... + n Z + n ∗ ). Angenommen, Sie hätten ein Wörterbuch mit einer begrenzten Anzahl von Wörtern. Sie wählen k Fliesen aus dem Beutel ohne Ersatz. Wie würden Sie die Wahrscheinlichkeit berechnen (oder schätzen), dass Sie mit den ausgewählten k Kacheln aus dem Wörterbuch null Wörter bilden können ?$n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$$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.

Um eine Vorstellung von der Größe des Problems zu bekommen, ist klein, wie 7, n ist ungefähr 100, und das Wörterbuch enthält ungefähr 100.000 Wörter der Größe k oder kleiner.$k$$n$$k$

edit: Mit 'ein Wort bilden' meine ich ein Wort mit einer Länge von nicht mehr als . Befindet sich das Wort [ A ] im Wörterbuch, so hat man durch Ziehen eines einzigen "A" aus der Tasche ein "Wort gebildet". Das Problem der Platzhalter wird radikal vereinfacht, wenn man davon ausgehen kann, dass das Wörterbuch Wörter der Länge 1 enthält. Denn wenn es welche gibt, kann jedes Ziehen eines Platzhalters automatisch einem Wort der Länge 1 entsprechen und man kann sich auf den Fall konzentrieren, in dem es keine Platzhalter gibt. Daher enthält die rutschigere Form des Problems keine Wörter mit einem Buchstaben im Wörterbuch.$k$

Ich möchte auch ausdrücklich darauf hinweisen, dass die Reihenfolge, in der die Buchstaben aus der Tüte gezogen werden, unerheblich ist. Man muss die Buchstaben nicht in der "richtigen" Reihenfolge des Wortes zeichnen.

Dies ist ein (langer!) Kommentar zu der schönen Arbeit, die @vqv in diesem Thread gepostet hat. Es zielt darauf ab, eine endgültige Antwort zu erhalten. Er hat die harte Arbeit geleistet, das Wörterbuch zu vereinfachen. Alles, was bleibt, ist es, es in vollen Zügen zu nutzen. Seine Ergebnisse legen nahe, dass eine Brute-Force-Lösung möglich ist . Immerhin, einschließlich eines Platzhalters, gibt es höchstens Wörter, die man mit 7 Zeichen machen kann, und es sieht so aus, als ob weniger als 1/10000 von ihnen - sagen wir, ungefähr eine Million - werden Fehlt ein gültiges Wort. $27^7 = 10,460,353,203$

Der erste Schritt besteht darin, das minimale Wörterbuch mit einem Platzhalterzeichen "?" Zu erweitern. 22 der Buchstaben erscheinen in aus zwei Buchstaben bestehenden Wörtern (alle außer c, q, v, z). Fügen Sie diesen 22 Buchstaben einen Platzhalter hinzu und fügen Sie diese in das Wörterbuch ein: {a ?, b ?, d ?, ..., y?} Sind jetzt drin. Auf ähnliche Weise können wir die minimalen Wörter mit drei Buchstaben untersuchen und einige zusätzliche Wörter verursachen im Wörterbuch erscheinen. Schließlich fügen wir "??" zum Wörterbuch. Nach dem Entfernen von Wiederholungen enthält es 342 minimale Wörter.

Eine elegante Methode, um fortzufahren - eine, die in der Tat nur sehr wenig Codierung verwendet - besteht darin , dieses Problem als algebraisch anzusehen . Ein Wort, das als ungeordnete Buchstabenfolge betrachtet wird, ist nur ein Monom. Beispielsweise ist "Gamaschen" das Monom . Das Wörterbuch ist daher eine Sammlung von Monomen. Es sieht aus wie$a p s^2 t$

$$\{a^2, a b, a d, ..., o z \psi, w x \psi, \psi^2\}$$

(Um Verwechslungen zu vermeiden, habe ich für das Platzhalterzeichen geschrieben).$\psi$

Ein Rack enthält nur dann ein gültiges Wort, wenn dieses Wort das Rack unterteilt.

Eine abstraktere, aber äußerst leistungsfähige Art zu sagen ist, dass das Wörterbuch ein ideales im Polynomring R = Z [ a , b , … , z , ψ ] erzeugt und dass die Racks mit gültigen Wörtern im Quotienten Null werden Ring R / I , während Racks ohne gültige Wörter im Quotienten ungleich Null bleiben. Wenn wir die Summe aller Racks in R bilden und in diesem Quotientenring berechnen, entspricht die Anzahl der Racks ohne Wörter der Anzahl der verschiedenen Monome im Quotienten.$I$$R = \mathbb{Z}[a, b, \ldots, z, \psi]$$R/I$$R$

Darüber hinaus ist die Summe aller Racks in einfach auszudrücken. Sei α = a + b + ⋯ + z + ψ die Summe aller Buchstaben im Alphabet. α 7 enthält ein Monom für jedes Rack. (Als zusätzlichen Bonus zählen die Koeffizienten die Anzahl der Arten, wie jedes Rack gebildet werden kann, so dass wir seine Wahrscheinlichkeit berechnen können, wenn wir möchten.)$R$$\alpha = a + b + \cdots + z + \psi$$\alpha^7$

Als einfaches Beispiel (um zu sehen, wie dies funktioniert) nehmen wir an, dass (a) wir keine Platzhalter verwenden und (b) alle Buchstaben von "a" bis "x" als Wörter betrachtet werden. Dann müssen die einzig möglichen Gestelle, aus denen Wörter nicht gebildet werden können, vollständig aus ys und zs bestehen. Wir berechnen modulo das Ideal, das von { a , b , c , … , x } schrittweise erzeugt wird, also:$\alpha=(a+b+c+\cdots+x+y+z)^7$$\{a,b,c, \ldots, x\}$

$$\eqalign{ \alpha^0 &= 1 \cr \alpha^1 &= a+b+c+\cdots+x+y+z \equiv y+z \mod I \cr \alpha^2 &\equiv (y+z)(a+b+\cdots+y+z) \equiv (y+z)^2 \mod I \cr \cdots &\cr \alpha^7 &\equiv (y+z)^6(a+b+\cdots+y+z) \equiv (y+z)^7 \mod I \text{.} }$$

Aus der endgültigen Antwort können wir die Wahrscheinlichkeit ablesen, dass ein Nicht-Wort-Rack entsteht: : Jeder Koeffizient zählt die Möglichkeiten, wie das entsprechende Rack gezeichnet werden kann. Zum Beispiel gibt es 21 (von 26 ^ 7 möglichen) Möglichkeiten, 2 ys und 5 zs zu zeichnen, weil der Koeffizient von $y^7 + 7 y^6 z + 21 y^5 z^2 + 35 y^4 z^3 + 35 y^3 z^4 + 21 y^2 z^5 + 7 y z^6 + z^7$ entspricht 21.$y^2 z^5$

Aus elementaren Berechnungen geht hervor, dass dies die richtige Antwort ist. Der springende Punkt ist, dass dieses Verfahren unabhängig vom Inhalt des Wörterbuchs funktioniert.

Beachten Sie, wie das Reduzieren des Leistungsmoduls auf jeder Stufe die Berechnung reduziert: Dies ist die Abkürzung, die durch diesen Ansatz aufgedeckt wird. (Ende des Beispiels)

Polynomalgebrasysteme implementieren diese Berechnungen . Hier ist zum Beispiel Mathematica- Code:

alphabet =  a + b + c + d + e + f + g + h + i + j + k + l + m + n + o + 
            p + q + r + s + t + u + v + w + x + y + z + \[Psi];
dictionary = {a^2, a b, a d, a e, ..., w z \[Psi], \[Psi]^2};
next[pp_] := PolynomialMod[pp alphabet, dictionary];
nonwords = Nest[next, 1, 7];
Length[nonwords]

(Das Wörterbuch kann auf einfache Weise aus @ vqvs min.dict erstellt werden. Ich habe hier eine Zeile eingefügt, die zeigt, dass es kurz genug ist, um direkt angegeben zu werden, wenn Sie möchten.)

Der Ausgang - die 10 Minuten der Berechnung nimmt - ist 577958. ( NB In einer früheren Version dieser Nachricht hatte ich einen kleinen Fehler bei der Vorbereitung des Wörterbuch gemacht und erhielt 577940. Ich habe den Text bearbeitet zu reflektieren , was ich hoffe , ist jetzt die richtigen Ergebnisse!) Etwas weniger als die Millionen, die ich erwartet hatte, aber in der gleichen Größenordnung.

Um die Wahrscheinlichkeit zu berechnen , ein solches Rack zu erhalten, müssen wir die Anzahl der Möglichkeiten berücksichtigen, mit denen das Rack gezeichnet werden kann. Wie wir im Beispiel gesehen haben, entspricht dies seinem Koeffizienten in . Die Chance, ein solches Rack zu ziehen, ist die Summe aller dieser Koeffizienten, die leicht zu finden sind, wenn alle Buchstaben gleich 1 gesetzt werden:$\alpha^7$

nonwords /. (# -> 1) & /@ (List @@ alphabet)

Die Antwort ist gleich 1066056120, was eine Chance von 10,1914% des Zeichnens eines Racks ergibt, aus dem kein gültiges Wort gebildet werden kann (wenn alle Buchstaben gleich wahrscheinlich sind).

Wenn die Wahrscheinlichkeiten der Buchstaben variieren, ersetzen Sie einfach jeden Buchstaben durch die Wahrscheinlichkeit, dass er gezogen wird:

tiles = {9, 2, 2, 4, 12, 2, 3, 2, 9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4, 6, 
         4, 2, 2, 1, 2, 1, 2};
chances = tiles / (Plus @@ tiles);
nonwords /. (Transpose[{List @@ alphabet, chances}] /. {a_, b_} -> a -> b)

Die Ausgabe ist 1.079877553303%, die genaue Antwort (wenn auch unter Verwendung eines ungefähren Modells, Zeichnung mit Ersatz). Rückblickend dauerte es vier Zeilen, um die Daten einzugeben (Alphabet, Wörterbuch und Alphabethäufigkeiten), und nur drei Zeilen, um die Arbeit zu erledigen: Beschreiben Sie, wie Sie die nächste Potenz von modulo I nehmen, die siebte Potenz rekursiv nehmen und die ersetzen Wahrscheinlichkeiten für die Buchstaben.$\alpha$$I$

Es ist sehr schwierig, ein Rack zu zeichnen, das in Scrabble und seinen Varianten kein gültiges Wort enthält. Unten ist ein R-Programm, das ich geschrieben habe, um die Wahrscheinlichkeit zu schätzen, dass das anfängliche 7-Felder-Rack kein gültiges Wort enthält. Es verwendet einen Monte Carlo-Ansatz und das Words With Friends- Lexikon (ich konnte das offizielle Scrabble-Lexikon nicht in einem einfachen Format finden). Jeder Versuch besteht darin, ein Rack mit 7 Feldern zu zeichnen und dann zu überprüfen, ob das Rack ein gültiges Wort enthält.

Minimale Wörter

Sie müssen nicht das gesamte Lexikon durchsuchen, um zu überprüfen, ob das Rack ein gültiges Wort enthält. Sie müssen nur ein minimales Lexikon scannen, das aus minimalen Wörtern besteht. Ein Wort ist minimal, wenn es kein anderes Wort als Teilmenge enthält. Zum Beispiel 'em' ist ein minimales Wort; "leer" ist nicht. Der Punkt dabei ist, dass ein Rack, wenn es das Wort x enthält, auch eine Teilmenge von x enthalten muss . Mit anderen Worten: Ein Rack enthält keine Wörter, wenn es keine minimalen Wörter enthält. Glücklicherweise sind die meisten Wörter im Lexikon nicht minimal und können daher entfernt werden. Sie können auch permutationsäquivalente Wörter zusammenführen. Ich konnte das Lexikon Words With Friends von 172.820 auf 201 minimale Wörter reduzieren.

$\leq$

$N=100,000$

Ich würde gerne sehen, ob jemand einen effizienten exakten Algorithmus entwickeln kann. Ein naiver Ansatz, der auf Inklusion und Exklusion basiert, könnte eine kombinatorische Explosion beinhalten.

Inklusion Exklusion

Ich halte das für eine schlechte Lösung, aber hier ist trotzdem eine unvollständige Skizze. Im Prinzip kann man ein Programm schreiben, um die Berechnung durchzuführen, aber die Spezifikation wäre mühsam.

$$P(k\text{-tile rack does not contain a word}) = 1 - P(k\text{-tile rack contains a word}) .$$ $$P(k\text{-tile rack contains a word}) = P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right),$$ $M$$\mathcal{P}(M)$$M$$M$ $$\begin{align} &P(k\text{-tile rack contains a word}) \\ &= P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{j=1}^{|M|} (-1)^{j-1} \sum_{S \in \mathcal{P}(M) : |S| = j} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \end{align}$$

$$\cap_{x \in S} \{ k\text{-tile rack contains }x \}$$ $S$

Dann

$$\begin{align} &P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{w=0}^{n_{*}} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} | k\text{-tile rack contains } w \text{ wildcards} \right) \\ &\quad \times P(k\text{-tile rack contains } w \text{ wildcards}) . \end{align}$$

$2^{|M|}$$2^{|M|} \approx 3.2 \times 10^{60}$

Scannen aller möglichen Racks

$k$-Racks kacheln, bis wir den Satz von Racks erhalten, die keine Wörter enthalten. Bei Scrabble (oder Words With Friends) liegt die Anzahl der möglichen 7-Kacheln-Racks bei mehreren zehn Milliarden. Das Zählen der Anzahl derer, die kein mögliches Wort enthalten, sollte mit ein paar Dutzend Zeilen R-Code möglich sein. Aber ich denke, Sie sollten es besser machen können, als nur alle möglichen Racks aufzulisten. Zum Beispiel ist 'aa' ein Minimalwort. Dadurch werden alle Racks, die mehr als ein 'a' enthalten, sofort entfernt. Sie können mit anderen Worten wiederholen. Speicher sollte für moderne Computer kein Problem sein. Ein Scrabble-Rack mit 7 Kacheln benötigt weniger als 7 Byte Speicherplatz. Im schlimmsten Fall würden wir ein paar Gigabyte zum Speichern aller möglichen Racks verwenden, aber ich halte das auch nicht für eine gute Idee. Vielleicht möchte jemand mehr darüber nachdenken.

Monte Carlo R-Programm

# 
#  scrabble.R
#  
#  Created by Vincent Vu on 2011-01-07.
#  Copyright 2011 Vincent Vu. All rights reserved.
# 

# The Words With Friends lexicon
# http://code.google.com/p/dotnetperls-controls/downloads/detail?name=enable1.txt&can=2&q=
url <- 'http://dotnetperls-controls.googlecode.com/files/enable1.txt'
lexicon <- scan(url, what=character())

# Words With Friends
letters <- c(unlist(strsplit('abcdefghijklmnopqrstuvwxyz', NULL)), '?')
tiles <- c(9, 2, 2, 5, 13, 2, 3, 4, 8, 1, 1, 4, 2, 5, 8, 2, 1, 6, 5, 7, 4, 
           2, 2, 1, 2, 1, 2)
names(tiles) <- letters

# Scrabble
# tiles <- c(9, 2, 2, 4, 12, 2, 3, 2, 9, 1, 1, 4, 2, 6, 8, 2, 1, 6, 4, 6, 4, 
#            2, 2, 1, 2, 1, 2)


# Reduce to permutation equivalent words
sort.letters.in.words <- function(x) {
  sapply(lapply(strsplit(x, NULL), sort), paste, collapse='')
}

min.dict <- unique(sort.letters.in.words(lexicon))
min.dict.length <- nchar(min.dict)

# Find all minimal words of length k by elimination
# This is held constant across iterations:
#   All words in min.dict contain no other words of length k or smaller
k <- 1
while(k < max(min.dict.length))
{
  # List all k-letter words in min.dict
  k.letter.words <- min.dict[min.dict.length == k]

  # Find words in min.dict of length > k that contain a k-letter word
  for(w in k.letter.words)
  {
    # Create a regexp pattern
    makepattern <- function(x) {
      paste('.*', paste(unlist(strsplit(x, NULL)), '.*', sep='', collapse=''), 
            sep='')
    }
    p <- paste('.*', 
               paste(unlist(strsplit(w, NULL)), 
                     '.*', sep='', collapse=''), 
               sep='')

    # Eliminate words of length > k that are not minimal
    eliminate <- grepl(p, min.dict) & min.dict.length > k
    min.dict <- min.dict[!eliminate]
    min.dict.length <- min.dict.length[!eliminate]
  }
  k <- k + 1
}

# Converts a word into a letter distribution
letter.dist <- function(w, l=letters) {
  d <- lapply(strsplit(w, NULL), factor, levels=l)
  names(d) <- w
  d <- lapply(d, table)
  return(d)
}

# Sample N racks of k tiles
N <- 1e5
k <- 7
rack <- replicate(N,
                  paste(sample(names(tiles), size=k, prob=tiles), 
                        collapse=''))

contains.word <- function(rack.dist, lex.dist)
{
  # For each word in the lexicon, subtract the rack distribution from the 
  # letter distribution of the word.  Positive results correspond to the 
  # number of each letter that the rack is missing.
  y <- sweep(lex.dist, 1, rack.dist)

  # If the total number of missing letters is smaller than the number of 
  # wildcards in the rack, then the rack contains that word
  any(colSums(pmax(y,0)) <= rack.dist[names(rack.dist) == '?'])
}

# Convert rack and min.dict into letter distributions
min.dict.dist <- letter.dist(min.dict)
min.dict.dist <- do.call(cbind, min.dict.dist)
rack.dist <- letter.dist(rack, l=letters)

# Determine if each rack contains a valid word
x <- sapply(rack.dist, contains.word, lex.dist=min.dict.dist)

message("Estimate (and SE) of probability of no words based on ", 
        N, " trials:")
message(signif(1-mean(x)), " (", signif(sd(x) / sqrt(N)), ")")

$1$$k$

Der zweite Grund ist, dass MC tatsächlich machbar ist: Sie müssen es einfach richtig machen. Der vorstehende Absatz gibt einen Hinweis: Generieren Sie Wörter nicht einfach nach dem Zufallsprinzip und schlagen Sie sie nach. Analysieren Sie stattdessen zuerst das Wörterbuch und nutzen Sie dessen Struktur aus.

$k!-1$

$k$ ordnen Sie die Elemente zunächst in sortierter Reihenfolge an.Suchen Sie dann nach diesem sortierten "Wort" in einem Baum, der aus den sortierten Vertretern der Wörter im ursprünglichen Wörterbuch erstellt wurde. Dies ist tatsächlich kleiner als der ursprüngliche Baum, da alle sortierungsäquivalenten Wortgruppen zusammengeführt werden, z. B. {stop, post, pots, opts, spot}. Tatsächlich würde in einem englischen Wörterbuch diese Klasse von Wörtern sowieso nie erreicht werden, weil "so" zuerst gefunden würde. Lassen Sie uns dies in Aktion sehen. Das sortierte Multiset ist "opst"; das "o" würde zu allen Wörtern verzweigen, die nur die Buchstaben {o, p, ..., z} enthalten, das "p" würde zu allen Wörtern verzweigen, die nur {o, p, ..., z} enthalten und höchstens ein "o", und schließlich würde das "s" zum Blatt "so" verzweigen! (Ich habe angenommen, dass keiner der plausiblen Kandidaten "o", "op", "

Eine Modifikation ist erforderlich, um mit Platzhaltern umzugehen: Ich lasse die Programmierertypen unter Ihnen darüber nachdenken. Die Wörterbuchgröße wird nicht vergrößert (es sollte sie tatsächlich verkleinern). Dadurch wird die Durchquerung des Baums etwas verlangsamt, ohne dass dies grundlegend geändert wird. In jedem Wörterbuch, das ein Wort mit einem Buchstaben enthält, wie in Englisch ("a", "i"), gibt es keine Komplikationen: Das Vorhandensein eines Platzhalters bedeutet, dass Sie ein Wort bilden können! (Dies deutet darauf hin, dass die ursprüngliche Frage möglicherweise nicht so interessant ist, wie es sich anhört.)

$k$$k$$O(k \log(k))$$O(k)$

Ich wette, Sie könnten diese Studie mit einem echten Scrabble-Set und einer Million Iterationen in Sekunden durchführen.

Monte-Carlo-Ansatz

$k$$m$$k$$m_w$

$$1 - \frac{m_w}{m}$$

Direkte Annäherung

$S$$t_s$$s^\mbox{th}$$s^\mbox{th}$${m_a, m_b, ..., m_z}$$s^\mbox{th}$$m_a$$N$

$$N = \binom{n}{k}$$

und

$$t_s = \binom{n_a}{m_a} \binom{n_b}{m_b} ... \binom{n_z}{m_z}$$

(Einschließlich der Auswirkungen von Wildcard-Kacheln ist ein bisschen kniffliger. Ich werde dieses Problem vorerst aufschieben.)

Die gewünschte Wahrscheinlichkeit ist also:

$$1 - \frac{\sum_s{t_s}}{N}$$