Wahrscheinlichkeit, ein bestimmtes Wort aus einer Buchstabenkiste in Scrabble zu ziehen

18

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

Sie wählen Fliesen aus dem Beutel ohne Ersatz.k

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 kllkk

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

Sébastien
quelle
Ich würde raten, zunächst einen einfacheren Fall zu behandeln, z. B. einen ohne Platzhalter.
Glen_b -Reinstate Monica
@ Glen_b Ich stimme zu. Da mein letztes Ziel darin besteht, die Wörter nach Wahrscheinlichkeit zu ordnen, halte ich das Ignorieren der Platzhalter für eine akzeptable Annäherung. Ich bin jedoch immer noch nicht in der Lage, eine Formel zu erstellen, um dieses einfachere Problem zu lösen
Sébastien,
1
Wenn Sie noch einfacher beginnen möchten, berechnen Sie die Wahrscheinlichkeit, B, dann O, dann O und dann T auszuwählen. Berechnen Sie anschließend die Wahrscheinlichkeit, dass die Buchstaben in beliebiger Reihenfolge ausgewählt werden. Berücksichtigen Sie danach, dass Sie sieben Versuche haben. Dann berücksichtigen Sie die Platzhalter.
Jerry Schirmer
1
Eine einfache Möglichkeit, dieses Problem zu lösen, wäre die Verwendung einer Monte-Carlo-Näherung. Würde das ausreichen?
Rasmus Bååth
1
Sprechen Sie über das Bilden von Wörtern nur mit den Buchstaben, die Sie auswählen, oder unter Berücksichtigung der bereits ausgewählten Buchstaben und Wörter, die bereits auf der Tafel platziert sind?
Samthebrand

Antworten:

12

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 ,mwr=7NMW=2(m,w)

(Mm)(Ww)(NMWrmw)

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 6wrmww=0m=3286"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":

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

  2. 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 ist RCode für den rekursiven Schritt. rackin 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.7wordc(b=1, o=2, t=1)alphabetwild

f <- function(rack, word, alphabet, wild) {
  if (length(word) == 1) {
    return(ifelse(word > rack+wild, 0, choose(alphabet, rack)))
  }
  n <- word[1]
  if (n <= 0) return(0)
  m <- alphabet[1]
  x <- sapply(max(0, n-wild):min(m, rack), 
              function(i) {
                choose(m, i) * f(rack-i, word[-1], alphabet[-1], wild-max(0, n-i))
              })
  return(sum(x))
}

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 ( Mmw und ( W(Mm) werden berechnet und multipliziert.(Ww)

scrabble <- function(sword, n.wild=2, rack=7, 
              alphabet=c(a=9,b=2,c=2,d=4,e=12,f=2,g=3,h=2,i=9,j=1,k=1,l=4,m=2,
                         n=6,o=8,p=2,q=1,r=6,s=4,t=6,u=4,v=2,w=2,x=1,y=2,z=1),
              N=sum(alphabet)+n.wild) {
  word = sort(table(strsplit(sword, NULL))) # Sorting speeds things a little
  a <- sapply(names(word), function(s) alphabet[s])
  names(a) <- names(word)
  x <- sapply(0:n.wild, function(w) {
    sapply(sum(word):rack-w, 
           function(i) {
             f(i, word, a, wild=w) *
               choose(n.wild, w) * choose(N-n.wild-sum(a), rack-w-i)
           })
  })
  return(list(numerator = sum(x), denominator = choose(N, rack),
              value=sum(x) / choose(N, rack)))
}

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 :

system.time(x <- sapply(c("boot", "red", "axe", "zoology"), scrabble))

Dieses Gerät meldet eine Gesamtzeit von Sekunden: ziemlich schnell. Die Ergebnisse?0.05

> x
            boot        red         axe         zoology     
numerator   114327888   1249373480  823897928   11840       
denominator 16007560800 16007560800 16007560800 16007560800 
value       0.007142118 0.07804896  0.0514693   7.396505e-07

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/160075608002381831/33349085011840/16007560800,

whuber
quelle
Coole und elegante Lösung! Und viel schneller als meins ... :)
Rasmus Bååth
1
Dies ist eine großartige Antwort, danke. Ich hätte es schwer gehabt, Ihren Algorithmus zu codieren, daher ist der gebrauchsfertige Code sehr willkommen. Ich wusste es nicht, habe es Raber 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)
Sébastien
16

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.

  1. 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.“χ

    word = {b, o, o, t};
    letters = {b, o, t, \[Chi], \[Psi]};
    tileCounts = {2, 8, 6, 82, 2};
    rack = 7;
  2. Erstellen Sie ein Wörterbuch dieses Wortes (oder dieser Wörter) und erweitern Sie es, um alle möglichen Platzhalter-Schreibweisen einzuschließen.

    dict[words_, nWild_Integer] := Module[{wildcard, w},
       wildcard = {xx___, _, yy___} -> {xx, \[Psi], yy};
       w = Nest[Flatten[ReplaceList[#, wildcard] & /@ #, 1] &, words, nWild];
       Union[Times @@@ Join[w, Times @@@ words]]];
    dictionary = dict[{word}, 2]

    {bo2t,bo2ψ,botψ,o2tψ,boψ2,o2ψ2,btψ2,otψ2}

  3. Berechnen Sie die Nichtwörter:

    alphabet = Plus @@ letters;
    nonwords = Nest[PolynomialMod[# alphabet, dictionary] &, 1, rack]

    b7+7b6o+21b5o2++7χψ6+ψ7

    185

  4. Berechnen Sie die Chancen. Ersetzen Sie für Stichproben mit Ersetzung einfach die Anzahl der Kacheln durch die Variablen:

    chances = (Transpose[{letters, tileCounts/(Plus @@ tileCounts)}] /. {a_, b_} -> a -> b);
    q = nonwords /. chances;
    1 - q

    20726341339062500000

    0.00756036.

    Verwenden Sie für die ersatzlose Abtastung Fakultätskräfte anstelle von Kräften:

    multiplicities = MapThread[Rule, {letters, tileCounts}];
    chance[m_] :=  (ReplaceRepeated[m , Power[xx_, n_] -> FactorialPower[xx, n]] 
                   /. multiplicities);
    histor = chance /@ MonomialList[nonwords];
    q0 = Plus @@ histor  / FactorialPower[Total[tiles], nn];
    1 - q0

    2381831333490850

    0.00714212.


Simulationsergebnisse

106

simulation = RandomChoice[tiles -> letters, {10^6, 7}];
u = Tally[Times @@@ simulation];
(p = Total[Cases[Join[{PolynomialMod[u[[All, 1]], dictionary]}\[Transpose], 
       u, 2], {0, _, a_} :> a]] / Length[simulation] ) // N

0.007438

Vergleichen Sie es mit dem berechneten Wert relativ zu seinem Standardfehler:

(p - (1 - q)) / Sqrt[q (1 - q) / Length[simulation]] // N

1.41259

Die Vereinbarung ist in Ordnung und stützt das berechnete Ergebnis nachdrücklich.

106

tilesAll = Flatten[MapThread[ConstantArray[#1, #2] &, {letters, tiles}] ]
    (p - (1 - q)) / Sqrt[q (1 - q) / Length[simulation]] // N;
simulation = Table[RandomSample[tilesAll, 7], {i, 1, 10^6}];
u = Tally[Times @@@ simulation];
(p0 = Total[Cases[Join[{PolynomialMod[u[[All, 1]], dictionary]}\[Transpose], 
       u, 2], {0, _, a_} :> a]] / Length[simulation] ) // N

0,00717

Machen Sie den Vergleich:

(p0 - (1 - q0)) / Sqrt[q0 (1 - q0) / Length[simulation]] // N

0,331106

Die Übereinstimmung in dieser Simulation war ausgezeichnet.

12

whuber
quelle
13

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.

# The tile frequency used in English Scrabble, using "_" for blank.
tile_freq <- c(2, 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)
tile_names <- as.factor(c("_", letters))
tiles <- rep(tile_names, tile_freq)
## [1] _ _ a a a a a a a a a b b c c d d d d e e e e e e
## [26] e e e e e e f f g g g h h i i i i i i i i i j k l
## [51] l l l m m n n n n n n o o o o o o o o p p q r r r
## [76] r r r s s s s t t t t t t u u u u v v w w x y y z
## 27 Levels: _ a b c d e f g h i j k l m n o p q r ... z

Codiere dann das Wort als einen Vektor der Buchstabenanzahl.

word <- "boot"
# A vector of the counts of the letters in the word
word_vector <- table( factor(strsplit(word, "")[[1]], levels=tile_names))
## _ 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 
## 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0 0 0 0 0 0 

Zeichnen Sie nun ein Muster von sieben Kacheln und kodieren Sie sie wie das Wort.

tile_sample <- table(sample(tiles, size=7))
## _ 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 
## 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 

Berechnen Sie endlich, welche Buchstaben fehlen ...

missing <- word_vector - tile_sample
missing <- ifelse(missing < 0, 0, missing)
## _ 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 
## 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 

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

sum(missing) - tile_sample["blank"] <= 0
## FALSE

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:

word_prob <- function(word, reps = 50000) {
  tile_freq <- c(2, 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)
  tile_names <- as.factor(c("_", letters))
  tiles <- rep(tile_names, tile_freq)
  word_vector <- table( factor(strsplit(word, "")[[1]], levels=tile_names))
  successful_draws <- replicate(reps, {
    tile_sample <- table(sample(tiles, size=7))
    missing <- word_vector - tile_sample
    missing <- ifelse(missing < 0, 0, missing)
    sum(missing) - tile_sample["_"] <= 0
  })
  mean(successful_draws)
}

Hier repsist die Anzahl der simulierten Ziehungen. Jetzt können wir verschiedene Wörter ausprobieren.

> word_prob("boot")
[1] 0.0072
> word_prob("red")
[1] 0.07716
> word_prob("axe")
[1] 0.05088
> word_prob("zoology")
[1] 2e-05
Rasmus Bååth
quelle
Ich bekomme unterschiedliche Antworten. Es ist schwer zu sagen, warum sie nicht übereinstimmen, angesichts der Komplexität Ihres Simulationscodes, aber ich würde bei unserem Umgang mit Platzhaltern nach der Ursache suchen.
Whuber
2
Ich glaube, das sampleverhä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 Sie size=7zu size=28, um dies herauszufinden.
Whuber
2
@whuber Du hast recht, danke für den Hinweis! Jetzt funktioniert es und liefert die gleiche Antwort wie Ihr Code!
Rasmus Bååth
Danke für diese nette Arbeit. In der Tat ist ein Monte-Carlo-Ansatz perfekt geeignet. Hauptsächlich aus Gründen der Leistung habe ich mich jedoch für den genauen Berechnungsalgorithmus von whuber entschieden.
Sébastien
7

Für das Wort "BOOT" ohne Platzhalter:

p0=(nb1)(nO2)(nt1)(n-43)(n7)
Mit Platzhaltern wird es mühsamer. Lassenpk Geben Sie die Wahrscheinlichkeit an, mit der Sie "BOOT" spielen können k Platzhalter:
p0=(nb1)(nO2)(nt1)(n-43)(n7)p1=p0+(n1)(nO2)(nt1)(n-43)(n7)+(nb1)(nO1)(n1)(nt1)(n-43)(n7)+(nb1)(nO2)(n1)(n-43)(n7)=p0+(n1)(n-43)(n7)((nO2)(nt1)+(nb1)(nO1)(nt1)+(nb1)(nO2))p2=p1+(n2)(n-43)(n7)((nb1)(nO1)+(nb1)(nt1)+(nO2)+(nO1)(nt1))p3=p2+(n3)(n-43)(n7)((nb1)+(nO1)+(nt1))p4=p3+(n4)(n-43)(n7)pich=p4,ich4
Clintonmonk
quelle
Die Idee ist richtig (obwohl es hilfreich wäre, das Warum und die Notation zu erklären, insbesondere was genau "n"bedeutet: ob alle anderen Buchstaben oder alle anderen Buchstaben und die Platzhalter gezählt werden), aber die Behandlung von Platzhaltern ist unvollständig. Ohne jede Erklärung und ohne Beispiele ist es schwierig festzustellen, ob Ihre Formeln korrekt sind, so dass wir sie berücksichtigen müssen unzuverlässig Im Allgemeinen ist es möglich, eine Formel für die Wahrscheinlichkeit in Form von Produktsummen von Binomialkoeffizienten aufzuschreiben.
Whuber
1
Es gibt Fehler bei der Berechnung von p0: Es wird davon ausgegangen, dass genau 1 "b", 2 "o" und 1 "t" ausgewählt werden. und dann nimmt es an, dass die Wahl der anderen drei Buchstaben unabhängig von diesen Wahlmöglichkeiten sein wird, was es nicht ist. Vorausgesetztn=100 ist die Gesamtzahl der Kacheln, der resultierende Wert ist größer als er sein sollte (er ist gleich 8/25850,0031). Derselbe Fehler wird in die Berechnungen der Platzhalterwahrscheinlichkeiten übernommen.
Whuber
-1

Meh.

γc=b0xcln(x)r=0(c+y-1)(c+α)r(c+β)r(c+1)r(c+γ)rxr+

+b0xcr=0(c+γ-1)(c+α)r(c+β)r(c+1)r(c+γ)r(1c+γ-1+

+k=0r-1(1c+α+κ+1c+β+κ+1c+1+κ-1c+γ+κ))xr

=b0xcr=0(c+γ-1)(c+α)r(c+β)r(c+1)r(c+γ)r(ln x+1c+γ-1+

+k=0r-1(1c+α+κ+1c+β+κ-1c+1+κ-1c+γ+κ))xr
.

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.

// All arranged by letter, number of letters in scrabble game, and point for the letter.
$all = array("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");
    $count = array("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");
$point = array("1", "3", "3", "2", "1", "4", "2", "4", "1", "8", "5", "1", "3", "1", "1", "3", "10", "1", "1", "1", "1", "4", "4", "8", "4", "10");

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

let C(n,r) be binomial coefficient: n!/[n!(n-r)!], or 0 if r > n

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

B=(21)=2!2!(2-1)!
O=(82)=8!8!(8-2)!
T=(61)=6!6!(6-1)!

B×O×T dividiert durch den Binomialkoeffizienten von tilecount 98!98!(98-lenGth)!

James Cordeiro
quelle
Es ist schwer, Ihre Lösung zu bewerten, ohne zu wissen, was n und rsiehe in der endgültigen Formel. Wie gehen Sie mit dem Effekt der leeren Kacheln um? Das macht dieses Problem schwierig. Ungeachtet dessen wäre es interessant, eine Demonstration zu sehen, die den Wert von38248840160075608000,00239ist falsch: Dies wurde mit der von Rmir geposteten Lösung erhalten. Versuchen Sie diese einsekündige RSimulation: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))))
whuber
Bei der Bearbeitung: Ein offensichtlicher Fehler ist, dass Ihre Berechnung die Anzahl der Leerzeichen überhaupt nicht berücksichtigt. Soweit ich aus Ihren Formeln ersehen kann, würde sich Ihre Antwort nicht ändern, wenn sich diese Zahl ändern würde (etwa von 2 auf 50). Das ist offensichtlich falsch. Ein weiteres Problem, mit dem Sie konfrontiert sind, besteht darin, zu erklären, wie Ihre Antwort mit drei anderen bereits veröffentlichten Antworten in Konflikt geraten kann, bei denen drei völlig unterschiedliche Techniken angewendet werden, die jedoch miteinander übereinstimmen (und mit Ihrer nicht übereinstimmen).
Whuber
Wenn Kombinationen - die Mathematik ist Binomialkoeffizienten. Also sei x die Anzahl der leeren Kacheln. Die einzige Mathematik, die sich ändert, ist n! - Werden Leerzeichen verwendet oder nicht? Wenn ja, addieren Sie die Anzahl der Leerzeichen zu n! da leer erlaubt 2 weitere optionen von jedem buchstaben möglich (n + x)! - wenn nicht, lass n! wie es ist. Ja? Nein? Wenn abhängig von der in diesem Fall eingestellten Sprachregel keine Leerzeichen verwendet werden, wird n! = 98 oder 100 mit. Jeder Buchstabe ohne Leerzeichen ist C (n, r), sonst mit Leerzeichen C ((n + x), r). In dem Array gibt es ein Leerzeichen - aber ich habe vergessen, in der Mathematik ein Leerzeichen zu setzen. Ändern Sie also einfach n, um mit Leerzeichen zu arbeiten. Ja?
James Cordeiro
Nein, deine Argumentation ist ungültig. Ich lade Sie ein, Ihre Formeln mit kleineren Zahlen auszuprobieren, damit Sie sehen können, wo sie schief gehen.
Whuber
Was meinst du mit kleineren Zahlen - whuber? Gib mir ein Beispiel. Wollen Sie damit sagen, dass Sie stattdessen Boot aus einem Satz von 10 Buchstaben ziehen, 1 b, 2 o, 1 t mit einem 1-Leerzeichen im Satz und 5 weiteren Buchstaben. Oder etwas ganz anderes. Ich bin kein Mathe-Major, aber es scheint, dass wir Pokerspieler geworden sind. Wir berechnen jetzt die Pokerquoten mit Scrabble-Plättchen, die keine Farben haben.
James Cordeiro