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

27

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 ?nnAnBnn=nA+nB++nZ+nkk

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.knk

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.

shabbychef
quelle
Sollte es nicht "Pick k Fliesen ohne Ersatz" sein? Sehr interessante Frage.
Hoppla. in der Tat sollte es.
Shabbychef
Soweit ich mich erinnere, erlaubt Scrabble keine Wörter mit einem Buchstaben, so dass zumindest dieser Teil des Problems gelöst ist;)
nico
1
@Nico guter Punkt, aber ich denke, das ist nur für die Mitte des Spiels. Wörter mit einem Buchstaben erfordern entweder nicht das Spielen eines Buchstabens oder erlauben es einem, irgendwo auf der Tafel einen einzelnen Buchstaben zu platzieren, beides ist eindeutig inakzeptabel. Ich dachte jedoch an den Eröffnungszug. Tatsächlich kann die Frage für diejenigen, die mit Scrabble vertraut sind, kompakt formuliert werden: "Wie hoch ist die Wahrscheinlichkeit, dass der erste Spieler passen muss?"
Shabbychef
@nico Danke für die Klarstellung. Theoretisch betrifft ein ähnliches Problem Wörterbücher, die alle möglichen Zwei-Buchstaben-Kombinationen als Wörter enthalten: Wenn dies der Fall ist, enthält jede Hand mit zwei oder mehr Buchstaben automatisch ein Wort. @ shabbychefs Kommentar zur Spielmitte zeigt, wie irrelevant die ursprüngliche Frage für die meisten von Scrabble ist, da Sie in der Spielmitte zusätzlich zu den 7 Buchstaben in Ihrem Text eine Reihe von Wortteilen (Präfixe, Suffixe und sogar Mittelteile) zur Verfügung haben Hand. Dies erhöht die Wahrscheinlichkeit, ein Wort zu sagen, erheblich.
Whuber

Antworten:

14

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. 277=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 wieaps2t

{a2,ab,ad,...,ozψ,wxψ,ψ2}

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

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.IR=Z[a,b,,z,ψ]R/IR

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α=a+b++z+ψα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:α=(a+b+c++x+y+z)7{a,b,c,,x}

α0=1α1=a+b+c++x+y+zy+zmodIα2(y+z)(a+b++y+z)(y+z)2modIα7(y+z)6(a+b++y+z)(y+z)7modI.

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 isty7+7y6z+21y5z2+35y4z3+35y3z4+21y2z5+7yz6+z7 entspricht 21.y2z5

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:α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.αI

whuber
quelle
+1 Es ist eine clevere Idee, das Lexikon zu erweitern und es dann wieder zu verkleinern. Die Algebra ist mir ein Rätsel, aber es scheint, als würden Sie eine multinomiale Wahrscheinlichkeit berechnen, anstatt eine hypergeometrische. Die Wahrscheinlichkeit ist also für die Probenahme mit Ersatz. Ich denke, das erklärt, warum Ihre Antwort von 1,08% so viel größer ist als meine Schätzung von 0,4%. Gibt es eine Möglichkeit, Ihren Ansatz für die ersatzlose Probenahme zu ändern?
vqv
2
@vqv Ja. Nachdem wir nun eine Liste von ungefähr einer halben Million Racks ohne Wörter haben, ist es einfach (durch Ändern der letzten beiden Codezeilen), die Wahrscheinlichkeit jedes Racks (ohne Ersatz) zu berechnen und das hypergeometrische Ergebnis zu erhalten. Die genaue Antwort entspricht 349870667877/80678106432000 = 0,43366% . Bei N = 100K-Versuchen liegt Ihre SE bei 0,021%, sodass Ihre Antwort zwischen 0,38% und 0,49% liegen sollte (zweiseitiger 99% -KI). Ich bin so froh, dass unsere Antworten übereinstimmen!
whuber
@whuber Könnten Sie die Berechnung mit der Kachelverteilung Words With Friends (WWF) ausführen? Meine Schätzung von 0,4% basiert auf dem WWF-Lexikon und der Verteilung der WWF-Kacheln. Ich denke, Sie verwenden die Scrabble-Kachel-Distribution mit dem WWF-Lexikon.
vqv
Hoppla. Die genaue Antwort lautet tatsächlich 349870675899 (Ich war 8022 wegen eines Fehlers in meinem Wörterbuch ausgeschaltet.) Dies macht zum Glück keinen praktischen Unterschied.
whuber
@vqv Ich bin nicht mit den verschiedenen Kachelverteilungen vertraut. Ich habe meins direkt aus deinem Code kopiert (und ich habe dein Wörterbuch benutzt) :-). Wenn Sie die Verteilung bei osxreality.com 2010 / 01 / 01 /… meinen , dann erhalte ich 1,15444% (mit Ersatz), 0,43366% (ohne Ersatz). Die zweite Zahl unterscheidet sich tatsächlich von den Scrabble-Frequenzen bei der achten signifikanten Zahl.
whuber
14

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.

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-tile rack does not contain a word)=1P(k-tile rack contains a word).
P(k-tile rack contains a word)=P(xM{k-tile rack contains x}),
MP(M)MM
P(k-tile rack contains a word)=P(xM{k-tile rack contains x})=j=1|M|(1)j1SP(M):|S|=jP(xS{k-tile rack contains x})


xS{k-tile rack contains x}
S

Dann

P(xS{k-tile rack contains x})=w=0nP(xS{k-tile rack contains x}|k-tile rack contains w wildcards)×P(k-tile rack contains w wildcards).

2|M|2|M|3.2×1060

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)), ")")
vqv
quelle
Wow ... sehr schönes Follow-up.
Matt Parker
Ich bin etwas überrascht, dass es auf 201 Wörter reduziert wurde. Obwohl für das erste gespielte Wort, akzeptieren unsere Hausregeln 'I' und 'A' als Wörter, was wahrscheinlich die Anzahl der minimalen Wörter weiter reduzieren würde. Ich hatte gehofft, dass jemand die Einschluss-Ausschluss-Analyse, die ziemlich haarig sein sollte,
kaputt macht
@shabbychef Das Lexikon enthält keine Wörter mit einem Buchstaben. Die meisten minimalen Wörter bestehen aus zwei und drei Buchstaben. Hier ist die vollständige Verteilung der minimalen Wortlängen: 2: 73, 3:86, 4:31, 5: 9, 6: 2. Die Wörter mit 6 Buchstaben sind: GLYCYL und SYZYGY.
8.
@shabbychef Ich habe meine Antwort so aktualisiert, dass sie eine Skizze eines genauen Einschluss-Ausschluss-Ansatzes enthält. Es ist schlimmer als haarig.
8.
Gute Arbeit! Ich liebe es, dass diese Frage, die als ein Satz gestellt werden könnte (für diejenigen mit ausreichendem Hintergrund), Monte Carlo, Einschluss-Ausschluss, DAGs, Suchbäume, Polynomalgebra hervorgebracht hat und dass Ihre Simulationen durch die Theorie von @ bestätigt werden. whuber. Prost!
Shabbychef
7

1k

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.)

kkO(klog(k))O(k)

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

whuber
quelle
@whuber Der Baum ist eine nette Idee (stimmt für diese Idee), aber würde es nicht viel Speicher erfordern? Ich denke, es hängt davon ab, wie vielfältig das Wörterbuch ist, aber ich schätze, dass für ein einigermaßen vielfältiges Wörterbuch viele Bäume erforderlich sind. Beispielsweise würde der Baum "b" für alle Wörter, die dies nicht tun, mit dem Buchstaben "b" anstelle von "a" beginnen habe 'ein' in ihnen. In ähnlicher Weise würde der "c" -Baum mit dem Buchstaben "c" für jene Wörter beginnen, die nicht "a" und "b", sondern "c" haben. Mein direkter Ansatz scheint einfacher zu sein, da alle Wörter im Wörterbuch einmal durchlaufen werden müssen, nicht wahr?
1
@Srikant: Der Baum würde wahrscheinlich viel weniger RAM benötigen, als zunächst das gesamte Wörterbuch zwischenzuspeichern. Sind Sie überhaupt besorgt über ein paar Megabyte RAM? Übrigens gibt es nur einen Baum, nicht viele: Sie alle wurzeln in dem leeren Wort. Ihr Ansatz erfordert, wie ich es verstanden habe, mehrere Durchsuchungen des Wörterbuchs (bis zu 7! Von ihnen) in jeder Iteration , was es, wie @shabbychef befürchtet, nicht praktikabel macht. Es wäre hilfreich, wenn Sie den Algorithmus, an den Sie denken, näher erläutern könnten, in dem Sie schreiben: "Sehen Sie, ob Sie ein Wort bilden können": Das verbirgt viele wichtige Details!
whuber
@whuber: Nachdem ich meinen Kommentar gepostet habe, wurde mir klar, dass es nur einen Baum gibt. Ich stimme zu, dass mein Vorschlag für Monte Carlo unscharf ist und dass Ihre Antwort genau beschreibt, wie man Monte Carlo in dieser Umgebung tatsächlich implementieren kann. Ich meinte eigentlich, dass der direkte Ansatz (siehe meine Antwort) tatsächlich einfacher sein könnte, da dieser Ansatz im Gegensatz zu einem Monte Carlo, der mehrere Tausend Iterationen im Baum erfordert, eine einmalige Operation im Wörterbuch erfordert. Ich frage mich nur über die relativen Vorzüge der Ansätze.
@Srikant Ich habe es unterlassen, Ihre direkte Herangehensweise zu kommentieren, da ich vermute, dass sie die falschen Antworten erhält. Es scheint nicht für die Wörterbuchstruktur verantwortlich zu sein, dh die Teilmengenbeziehungen zwischen Wörtern. Würde Ihre Formel beispielsweise die richtige Antwort von Null für alle Wörterbücher erhalten, die alle möglichen Ein-Buchstaben-Wörter enthalten?
Whuber
@whuber hmmm guter Punkt. Vielleicht beantworte ich die falsche Frage!
2

Monte-Carlo-Ansatz

kmkmw

1mwm

Direkte Annäherung

Stssthsthma,mb,...,mzsthmaN

N=(nk)

und

ts=(nama)(nbmb)...(nzmz)

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

Die gewünschte Wahrscheinlichkeit ist also:

1stsN

quelle
Die schnelle und schmutzige Annäherung kann möglicherweise nicht so schnell sein! Das Wörterbuch kann 100.000 Wörter enthalten, und die Suche nach einer Übereinstimmung der angegebenen Kacheln könnte eine Kodierungskatastrophe sein.
Shabbychef
@shabbychef Dies ist etwas, das sich gut für Rechtschreibprüfer eignet. Siehe zum Beispiel n3labs.com/pdf/lexicon-squeeze.pdf
@shabbychef Reg monte-carlo- Wenn das Wörterbuch sortiert ist, sollte eine Übereinstimmung ziemlich schnell sein, nein? Auf jeden Fall war der direkte Ansatz, den ich zuvor skizziert hatte, fehlerhaft. Ich habe es repariert. Das Problem bei meiner früheren Lösung war, dass dasselbe Wort auf verschiedene Arten gebildet werden kann (z. B. 'bat', 'b * t' usw.).
1
@shabbychef Nach weiteren Überlegungen stimme ich Ihnen zu, dass der Ansatz von Monte Carlo nicht funktionieren wird. Ein Problem ist, dass Sie herausfinden müssen, welche Wörter Sie tatsächlich mit den k-Kacheln bilden können, und das zweite ist, dass Sie mit den k-Kacheln mehrere Wörter bilden können. Die Berechnung dieser Kombinationen aus k Kacheln ist wahrscheinlich nicht so einfach.
1
@Srikant Danke. Ihre Formel scheint davon auszugehen, dass Sie alle k Buchstaben verwenden müssen, um das Wort zu bilden, aber ich glaube nicht, dass der OP danach fragt. (So ​​wird Scrabble sowieso nicht gespielt.) Mit dieser impliziten Annahme sind Sie auf dem richtigen Weg, müssen aber den Algorithmus ändern: Sie dürfen die Berechnung für Wörter im Wörterbuch, die Permutationen voneinander sind, nicht wiederholen. Beispielsweise dürfen Sie in Ihrer Formel nicht sowohl t_ {stop} als auch t_ {post} subtrahieren. (Dies ist eine einfach zu implementierende Modifikation.)
whuber