Probabilité de ne pas tirer un mot d'un sac de lettres en Scrabble

27

Supposons que vous ayez un sac avec tuiles, chacune avec une lettre dessus. Il y a tuiles avec la lettre 'A', avec 'B', et ainsi de suite, et 'wildcard' tuiles (nous avons ). Supposons que vous disposiez d'un dictionnaire avec un nombre fini de mots. Vous choisissez tuiles du sac sans remplacement. Comment calculeriez-vous (ou estimeriez-vous) la probabilité que vous puissiez former zéro mot à partir du dictionnaire étant donné les tuiles sélectionnées?nnAnBnn=nA+nB++nZ+nkk

Pour ceux qui ne connaissent pas Scrabble (TM), le caractère générique peut être utilisé pour correspondre à n'importe quelle lettre. Ainsi, le mot [ BOOT ] pourrait être «orthographié» avec les tuiles «B», «*», «O», «T».

Pour donner une idée de l'ampleur du problème, est petit, comme 7, est d'environ 100, et le dictionnaire contient environ 100 000 mots de taille ou moins.knk

modifier: Par «former un mot», je veux dire un mot de longueur ne dépassant pas . Ainsi, si le mot [ A ] est dans le dictionnaire, alors en tirant même un seul «A» du sac, on a «formé un mot». Le problème des caractères génériques est radicalement simplifié si l'on peut supposer qu'il y a des mots de longueur 1 dans le dictionnaire. Car s'il y en a, tout tirage d'un caractère générique peut automatiquement correspondre à un mot de longueur 1, et donc on peut se concentrer sur le cas où il n'y a pas de caractères génériques. Ainsi, la forme la plus glissante du problème n'a pas de mots à 1 lettre dans le dictionnaire.k

En outre, je dois déclarer explicitement que l'ordre dans lequel les lettres sont tirées du sac est sans importance. Il n'est pas nécessaire de dessiner les lettres dans l'ordre «correct» du mot.

shabbychef
la source
Ne devrait-il pas s'agir de «choisir des tuiles k sans remplacement»? Question très intéressante.
Oops. en effet, il le devrait.
shabbychef
Autant que je me souvienne, Scrabble n'autorise pas les mots d'une seule lettre, donc au moins une partie du problème est résolue;)
nico
1
@nico bon point, mais je pense que ce n'est que pour le milieu de partie. Les mots à 1 lettre n'exigent pas que l'on joue une lettre, ou permettent de placer une seule lettre n'importe où sur le tableau, tous deux clairement inacceptables. Cependant, je pensais au mouvement d'ouverture. En fait, la question peut être formulée de manière compacte, pour ceux qui connaissent le Scrabble, comme "quelle est la probabilité que le premier joueur devra passer?"
shabbychef
@nico Merci pour cette précision. Théoriquement, un problème similaire se pose dans les dictionnaires contenant toutes les combinaisons possibles de deux lettres en tant que mots: dans ce cas, toute main de 2 lettres ou plus contient automatiquement un mot. Le commentaire de @ shabbychef sur le milieu du jeu montre à quel point la question d'origine est sans importance pour la plupart des Scrabble, car au milieu du jeu, vous disposez d'un tableau de parties de mots (préfixes, suffixes et même des sections centrales) en plus des 7 lettres de votre main. Cela augmente considérablement les chances de pouvoir faire un mot.
whuber

Réponses:

14

Ceci est un (long!) Commentaire sur le beau travail que @vqv a publié dans ce fil. Il vise à obtenir une réponse définitive. Il a fait le travail acharné de simplification du dictionnaire. Il ne reste plus qu'à l'exploiter au maximum. Ses résultats suggèrent qu'une solution de force brute est faisable . Après tout, y compris un caractère générique, il y a au plus mots que l'on peut faire avec 7 caractères, et il semble que moins de 1/10000 d'entre eux - disons, environ un million - ne pas inclure un mot valide. 277=dix,460,353,203

La première étape consiste à augmenter le dictionnaire minimal avec un caractère générique, "?". 22 des lettres apparaissent en deux lettres (toutes sauf c, q, v, z). Joignez un caractère générique à ces 22 lettres et ajoutez-les au dictionnaire: {a ?, b ?, d ?, ..., y?} Sont maintenant entrés. De même, nous pouvons inspecter les mots minimaux à trois lettres, provoquant quelques mots supplémentaires à apparaître dans le dictionnaire. Enfin, nous ajoutons "??" au dictionnaire. Après avoir supprimé les répétitions qui en résultent, il contient 342 mots minimum.

Une manière élégante de procéder - qui utilise en effet une très petite quantité d'encodage - est de considérer ce problème comme un problème algébrique . Un mot, considéré comme un ensemble de lettres non ordonné, n'est qu'un monôme. Par exemple, "spats" est le monôme . Le dictionnaire est donc une collection de monômes. Ça ressemble àuneps2t

{une2,uneb,une,...,ozψ,wXψ,ψ2}

(où, pour éviter toute confusion, j'ai écrit pour le caractère générique).ψ

Un rack contient un mot valide si et seulement si ce mot divise le rack.

Une façon plus abstraite, mais extrêmement puissante, de dire ceci est que le dictionnaire génère un idéal dans l'anneau polynomial R = Z [ a , b , , z , ψ ] et que les racks avec des mots valides deviennent nuls dans le quotient anneau R / I , tandis que les racks sans mots valides restent différents de zéro dans le quotient. Si nous formons la somme de tous les racks dans R et que nous la calculons dans cet anneau de quotient, alors le nombre de racks sans mots est égal au nombre de monômes distincts dans le quotient.jeR=Z[une,b,,z,ψ]R/IR

De plus, la somme de tous les racks en est simple à exprimer. Soit α = a + b + + z + ψ la somme de toutes les lettres de l'alphabet. α 7 contient un monôme pour chaque rack. (En prime, ses coefficients comptent le nombre de façons dont chaque rack peut être formé, ce qui nous permet de calculer sa probabilité si nous le voulons.)Rα=a+b++z+ψα7

À titre d'exemple simple (pour voir comment cela fonctionne), supposons (a) que nous n'utilisons pas de caractères génériques et (b) toutes les lettres de "a" à "x" sont considérées comme des mots. Ensuite, les seuls racks possibles à partir desquels les mots ne peuvent pas être formés doivent être entièrement composés de y et de z. On calcule modulo l'idéal généré par { a , b , c , , x } une étape à la fois, donc:α=(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)2modjeα7(y+z)6(une+b++y+z)(y+z)7modje.

Nous pouvons lire la possibilité d'obtenir un rack non mot à partir de la réponse finale, : chaque coefficient compte les façons dont le rack correspondant peut être dessiné. Par exemple, il existe 21 façons (sur 26 ^ 7 possibles) de dessiner 2 y et 5 z car le coefficient de yy7+7y6z+21y5z2+35y4z3+35y3z4+21y2z5+7yz6+z7 est égal à 21.y2z5

D'après les calculs élémentaires, il est évident que c'est la bonne réponse. Le fait est que cette procédure fonctionne quel que soit le contenu du dictionnaire.

Remarquez comment la réduction du module de puissance idéal à chaque étape réduit le calcul: c'est le raccourci révélé par cette approche. (Fin de l'exemple.)

Les systèmes d'algèbre polynomiale implémentent ces calculs . Par exemple, voici le code Mathematica :

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]

(Le dictionnaire peut être construit de manière simple à partir du min.dict de @ vqv; je mets ici une ligne montrant qu'il est suffisamment court pour être spécifié directement si vous le souhaitez.)

La sortie - qui prend dix minutes de calcul - est 577958. ( NB Dans une version antérieure de ce message, j'avais fait une petite erreur dans la préparation du dictionnaire et obtenu 577940. J'ai édité le texte pour refléter ce que j'espère être maintenant les résultats corrects!) Un peu moins que le million environ que j'attendais, mais du même ordre de grandeur.

Pour calculer les chances d'obtenir un tel rack, nous devons tenir compte du nombre de façons dont le rack peut être dessiné. Comme nous l'avons vu dans l'exemple, cela équivaut à son coefficient en . La chance de dessiner un tel rack est la somme de tous ces coefficients, facilement trouvée en mettant toutes les lettres égales à 1:α7

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

La réponse est égale à 1066056120, ce qui donne une chance de 10,1914% de dessiner un rack à partir duquel aucun mot valide ne peut être formé (si toutes les lettres sont également probables).

Lorsque les probabilités des lettres varient, il suffit de remplacer chaque lettre par sa chance d'être tirée:

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)

La sortie est 1,079877553303%, la réponse exacte (bien qu'en utilisant un modèle approximatif, dessin avec remplacement). Avec le recul, il a fallu quatre lignes pour saisir les données (alphabet, dictionnaire et fréquences de l'alphabet) et seulement trois lignes pour faire le travail: décrire comment prendre la prochaine puissance de modulo I , prendre la 7e puissance récursivement et remplacer la probabilités pour les lettres.αI

whuber
la source
+1 Joindre le lexique puis le minimiser est une idée intelligente. L'algèbre me dépasse, mais j'ai l'impression que vous calculez une probabilité multinomiale plutôt qu'hypergéométrique. La probabilité est donc pour l'échantillonnage avec remplacement. Je pense que cela explique pourquoi votre réponse de 1,08% est tellement plus grande que mon estimation de 0,4%. Existe-t-il un moyen de modifier votre approche pour gérer l'échantillonnage sans remplacement?
vqv
2
@vqv Oui. Maintenant que nous avons une liste du demi-million de racks sans mots, il est simple (en changeant les deux dernières lignes de code) de calculer les chances de chaque rack (sans remplacement) et d'obtenir le résultat hypergéométrique. La réponse exacte est égale à 349870667877/80678106432000 = 0,43366% . Avec les essais N = 100K, votre SE est de 0,021%, donc votre réponse aurait dû se situer entre 0,38% et 0,49% (IC bilatéral à 99%). Je suis tellement content que nos réponses soient d'accord!
whuber
@whuber Pourriez-vous exécuter le calcul en utilisant la distribution de tuiles Words With Friends (WWF)? Mon estimation de 0,4% est basée sur le lexique du WWF et la distribution des tuiles du WWF. Je pense que vous utilisez la distribution de tuiles Scrabble avec le lexique WWF.
vqv
Oops. La réponse exacte est en fait 349870675899 (j'étais 8022 éteint en raison d'une erreur dans mon dictionnaire.) Cela ne fait heureusement aucune différence pratique, heureusement.
whuber
@vqv Je ne connais pas les différentes distributions de tuiles. J'ai copié le mien directement depuis votre code (et j'ai utilisé votre dictionnaire) :-). Si vous parlez de la distribution sur osxreality.com/2010/01/01/… , alors j'obtiens 1,15444% (avec remplacement), 0,43366% (sans remplacement). Le deuxième nombre diffère en fait des fréquences de Scrabble au 8ème chiffre significatif.
whuber
14

Il est très difficile de dessiner un rack qui ne contient aucun mot valide dans Scrabble et ses variantes. Ci-dessous, un programme R que j'ai écrit pour estimer la probabilité que le rack initial de 7 cases ne contienne pas de mot valide. Il utilise une approche monte carlo et le lexique Words With Friends (je n'ai pas pu trouver le lexique officiel du Scrabble dans un format facile). Chaque essai consiste à dessiner un rack de 7 cases, puis à vérifier si le rack contient un mot valide.

Mots minimaux

Vous n'avez pas besoin de scanner l'intégralité du lexique pour vérifier si le rack contient un mot valide. Il vous suffit de scanner un lexique minimal composé de mots minimaux . Un mot est minimal s'il ne contient aucun autre mot comme sous-ensemble. Par exemple, «em» est un mot minimal; «vide» ne l'est pas. Le fait est que si un rack contient le mot x, il doit également contenir tout sous-ensemble de x . En d'autres termes: un rack ne contient aucun mot ssi il ne contient aucun mot minimal. Heureusement, la plupart des mots du lexique ne sont pas minimes, ils peuvent donc être éliminés. Vous pouvez également fusionner des mots équivalents à permutation. J'ai pu réduire le lexique Words With Friends de 172 820 à 201 mots minimum.

Les caractères génériques peuvent être facilement gérés en traitant les racks et les mots comme des distributions sur les lettres. Nous vérifions si un rack contient un mot en soustrayant une distribution de l'autre. Cela nous donne le nombre de chaque lettre manquante dans le rack. Si la somme de ces nombres est le nombre de caractères génériques, alors le mot est dans le rack.

Le seul problème avec l'approche de Monte Carlo est que l'événement qui nous intéresse est très rare. Il faut donc de nombreux essais pour obtenir une estimation avec une erreur standard suffisamment petite. J'ai couru mon programme (collé au fond) avec essais et a obtenu une probabilité estimée de 0,004 que le support ne contient pas un mot valide . L'erreur-type estimée de cette estimation est de 0,0002. Il n'a fallu que quelques minutes pour fonctionner sur mon Mac Pro, y compris le téléchargement du lexique.N=100,000

Je serais intéressé de voir si quelqu'un peut trouver un algorithme exact efficace. Une approche naïve basée sur l'inclusion-exclusion semble impliquer une explosion combinatoire.

Inclusion-exclusion

Je pense que c'est une mauvaise solution, mais voici quand même un croquis incomplet. En principe, vous pouvez écrire un programme pour effectuer le calcul, mais la spécification serait tortueuse.

La probabilité que nous souhaitons calculer est L'événement à l'intérieur de la probabilité sur le côté droit est une union d'événements: P ( k -rack de tuiles contient un mot ) = P ( x M { k -rack de tuiles contient  x } ) ,M

P(k-tile rack ne contient pas de mot)=1-P(k-tile rack contient un mot).
P(k-tile rack contient un mot)=P(XM{k-tile rack contient X}),
Mest un lexique minimal. Nous pouvons l'étendre en utilisant la formule d'inclusion-exclusion. Il s'agit de considérer toutes les intersections possibles des événements ci-dessus. Soit désignent l'ensemble d'alimentation de M , à savoir l'ensemble de tous les sous - ensembles possibles de M . ensuite P(M)MM
P(k-tile rack contient un mot)=P(XM{k-tile rack contient X})=j=1|M|(-1)j-1SP(M):|S|=jP(XS{k-tile rack contient X})


XS{k-tile rack contient X}
S

ensuite

P(XS{k-tile rack contient X})=w=0nP(XS{k-tile rack contient X}|k-tile rack contient w caractères génériques)×P(k-tile rack contient w caractères génériques).

2|M|2|M|3.2×dix60

Numérisation de tous les racks possibles

Je pense que c'est plus facile à calculer, car il y a moins de racks possibles que de sous-ensembles possibles de mots minimaux. On réduit successivement l'ensemble des possiblesk-tile racks jusqu'à ce que nous obtenions l'ensemble de racks qui ne contiennent aucun mot. Pour Scrabble (ou Words With Friends), le nombre de racks possibles à 7 cases est de l'ordre de dizaines de milliards. Compter le nombre de ceux qui ne contiennent pas de mot possible devrait être réalisable avec quelques dizaines de lignes de code R. Mais je pense que vous devriez pouvoir faire mieux que simplement énumérer tous les racks possibles. Par exemple, «aa» est un mot minimal. Cela élimine immédiatement tous les racks contenant plus d'un «a». Vous pouvez répéter avec d'autres mots. La mémoire ne devrait pas être un problème pour les ordinateurs modernes. Un rack Scrabble à 7 tuiles nécessite moins de 7 octets de stockage. Au pire, nous utiliserions quelques gigaoctets pour stocker tous les racks possibles, mais je ne pense pas que ce soit une bonne idée non plus. Quelqu'un voudra peut-être y réfléchir davantage.

Programme Monte Carlo R

# 
#  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
la source
Wow ... très bon suivi.
Matt Parker
Je suis quelque peu surpris qu'il ait été réduit à 201 mots. Bien que pour le premier mot joué, nos règles internes acceptent «I» et «A» comme mots, ce qui réduirait probablement davantage le nombre de mots minimaux. J'espérais voir quelqu'un sortir l'analyse d'inclusion-exclusion, qui devrait être assez poilue ...
shabbychef
@shabbychef Il n'y a pas de mots d'une lettre dans le lexique. La plupart des mots minimaux sont des mots de 2 et 3 lettres. Voici la distribution complète des longueurs minimales des mots: 2: 73, 3:86, 4:31, 5: 9, 6: 2. Les mots de 6 lettres sont: GLYCYL et SYZYGY.
vqv
@shabbychef J'ai mis à jour ma réponse pour inclure un croquis d'une approche exacte d'inclusion-exclusion. C'est pire que poilu.
vqv
bon travail! J'adore le fait que cette question, qui pourrait être posée en une phrase (à ceux qui ont une formation suffisante), a fait ressortir monte carlo, inclusion-exclusion, DAGs, recherche d'arbres, algèbre polynomiale, et que vos simulations soient confirmées par la théorie de @ Whuber. à votre santé!
shabbychef
7

Srikant a raison: une étude de Monte Carlo est la voie à suivre. Il y a deux raisons. Premièrement, la réponse dépend fortement de la structure du dictionnaire. Deux extrêmes sont (1) le dictionnaire contient tous les mots possibles d'une seule lettre. Dans ce cas, la chance de ne pas faire un mot dans un tirage au sort de1ou plusieurs lettres est zéro. (2) Le dictionnaire ne contient que des mots formés d'une seule lettre ( par exemple , "a", "aa", "aaa", etc. ). La chance de ne pas faire un mot dans un tirage au sortkles lettres sont facilement déterminées et sont évidemment non nulles. Toute réponse définitive sous forme fermée devrait incorporer toute la structure du dictionnaire et serait une formule vraiment horrible et longue.

La deuxième raison est que MC est en effet réalisable: il suffit de le faire correctement. Le paragraphe précédent fournit un indice: ne vous contentez pas de générer des mots au hasard et de les rechercher; au lieu de cela, analysez d'abord le dictionnaire et exploitez sa structure.

Une façon représente les mots du dictionnaire sous forme d'arbre. L'arbre est enraciné au symbole vide et se ramifie sur chaque lettre tout en bas; ses feuilles sont (bien sûr) les mots eux-mêmes. Cependant, nous pouvons également insérer toutes les permutations non triviales de chaque mot dans l'arbre (jusqu'àk!-1d'entre eux pour chaque mot). Cela peut être fait efficacement car il n'est pas nécessaire de stocker toutes ces permutations; seuls les bords de l'arborescence doivent être ajoutés. Les feuilles restent les mêmes. En fait, cela peut être simplifié davantage en insistant pour que l'arbre soit suivi dans l'ordre alphabétique .

En d'autres termes, pour déterminer si un multiset de kcaractères est dans le dictionnaire, organisez d'abord les éléments dans un ordre trié,puis recherchez ce «mot» trié dans un arbre construit à partir des représentants triés des mots dans le dictionnaire d'origine. Il sera en fait plus petit que l'arborescence d'origine car il fusionne tous les ensembles de mots qui sont équivalents au tri, tels que {stop, post, pots, opts, spot}. En fait, dans un dictionnaire anglais, cette classe de mots ne serait jamais atteinte de toute façon parce que "so" serait trouvé en premier. Voyons cela en action. Le multiset trié est "opst"; le "o" se ramifierait à tous les mots ne contenant que les lettres {o, p, ..., z}, le "p" se ramifierait à tous les mots ne contenant que {o, p, ..., z} et au plus un "o", et enfin le "s" se ramifierait à la feuille "so"! (J'ai supposé qu'aucun des candidats plausibles "o", "op", "

Une modification est nécessaire pour gérer les caractères génériques: je vais laisser les programmeurs parmi vous réfléchir à cela. Il n'augmentera pas la taille du dictionnaire (il devrait en fait le diminuer); il ralentira légèrement la traversée de l'arbre, mais sans le modifier de façon fondamentale. Dans tout dictionnaire qui contient un mot d'une seule lettre, comme l'anglais ("a", "i"), il n'y a pas de complication: la présence d'un caractère générique signifie que vous pouvez former un mot! (Cela laisse entendre que la question d'origine pourrait ne pas être aussi intéressante qu'elle y paraît.)

Le résultat est qu’une seule recherche dans un dictionnaire nécessite (a) de trier k-letter multiset et (b) traversant pas plus de kbords d'un arbre. Le temps de course estO(kbûche(k)). Si vous générez intelligemment des multisets aléatoires dans un ordre trié (je peux penser à plusieurs façons efficaces de le faire), le temps d'exécution se réduit àO(k). Multipliez cela par le nombre d'itérations pour obtenir la durée totale d'exécution.

Je parie que vous pourriez mener cette étude avec un vrai set de Scrabble et un million d'itérations en quelques secondes.

whuber
la source
@whuber L'arbre est une bonne idée (vote positif pour cette idée) mais ne nécessiterait-il pas beaucoup de mémoire? Je suppose que cela dépend de la diversité du dictionnaire, mais je suppose qu'un dictionnaire raisonnablement diversifié nécessiterait de nombreux arbres Par exemple, l'arbre «b» commencerait par la lettre «b» au lieu de «a» pour tous ces mots qui ne le sont pas. ont «un» en eux. De même, l'arbre «c» commencerait par la lettre «c» pour les mots qui n'ont pas «a» et «b» mais ont «c». Mon approche directe proposée semble plus simple car elle nécessite une traversée unique de tous les mots du dictionnaire, non?
1
@Srikant: L'arbre nécessiterait probablement beaucoup moins de RAM que la mise en cache de l'ensemble du dictionnaire pour commencer. Êtes-vous vraiment préoccupé par quelques mégaoctets de RAM, de toute façon? BTW, il n'y a qu'un seul arbre, pas beaucoup: ils sont tous enracinés dans le mot vide. Votre approche, telle que je l'ai comprise, nécessite plusieurs recherches dans le dictionnaire (jusqu'à 7! D'entre elles) à chaque itération , ce qui le rend impraticable comme @shabbychef le craint. Il serait utile que vous élaboriez l'algorithme que vous avez en tête lorsque vous écrivez «voyez si vous pouvez former un mot»: cela cache beaucoup de détails importants!
whuber
@whuber: J'ai réalisé qu'il n'y avait qu'un seul arbre après avoir posté mon commentaire. Reg mon approche - je suis d'accord que ma proposition de monte carlo est floue et votre réponse montre comment on peut réellement mettre en œuvre monte carlo dans ce cadre. En fait, je voulais dire que l' approche directe (voir ma réponse) peut en fait être plus simple car cette approche nécessite une opération unique sur le dictionnaire contrairement à un monte-carlo qui nécessite plusieurs milliers d'itérations sur l'arbre. Je me demande simplement sur les mérites relatifs des approches.
@Srikant Je me suis abstenu de commenter votre approche directe car je pense qu'elle obtient les mauvaises réponses. Il ne semble pas expliquer la structure du dictionnaire: c'est-à-dire les relations de sous-ensemble entre les mots. Par exemple, votre formule obtiendrait-elle la bonne réponse de zéro pour tous les dictionnaires contenant tous les mots possibles d'une lettre?
whuber
@whuber hmmm bon point. Peut-être que je réponds à la mauvaise question!
2

Approche de Monte Carlo

L'approche rapide et sale est de faire une étude à Monte Carlo. Dessinerk carrelage m fois et pour chaque tirage au sort kles tuiles voient si vous pouvez former un mot. Indiquez le nombre de fois que vous pourriez former un mot enmw. La probabilité souhaitée serait:

1-mwm

Approche directe

Soit le nombre de mots du dictionnaire donné par S. Laisserts être le nombre de façons dont nous pouvons former le semot. Soit le nombre de lettres nécessaire ause mot soit désigné par mune,mb,...,mz (c.-à-d. se besoins de mots munenombre de lettres «a», etc.). Indique le nombre de mots que nous pouvons former avec toutes les tuiles parN.

N=(nk)

et

ts=(nunemune)(nbmb)...(nzmz)

(Y compris l'impact des tuiles génériques est un peu plus délicat. Je vais reporter ce problème pour l'instant.)

Ainsi, la probabilité souhaitée est:

1-stsN

la source
L'approche rapide et sale peut ne pas être aussi rapide! Le dictionnaire peut contenir 100 000 mots, et la recherche d'une correspondance des tuiles données pourrait être une catastrophe de codage.
shabbychef
@shabbychef C'est quelque chose de bien fait pour convenir aux correcteurs orthographiques. Voir par exemple n3labs.com/pdf/lexicon-squeeze.pdf
@shabbychef Reg monte-carlo- si le dictionnaire est trié une correspondance devrait être assez rapide non? Quoi qu'il en soit, l'approche directe que j'ai décrite plus tôt était défectueuse. Je l'ai corrigé. Le problème dans ma solution précédente était que le même mot peut être formé de plusieurs façons (par exemple, 'bat', 'b * t' etc.).
1
@shabbychef Après réflexion, je suis d'accord avec vous que l'approche de Monte Carlo ne fonctionnera pas. Un problème est que vous devez déterminer quels mots vous pouvez réellement former avec les tuiles k et le second est que vous pouvez former plusieurs mots avec les tuiles k. Calculer ces combinaisons à partir de k tuiles n'est probablement pas si simple.
1
@Srikant Merci. Votre formule semble supposer que vous devez utiliser toutes les lettres k pour former le mot, mais je ne pense pas que c'est ce que le PO demande. (Ce n'est pas comme ça que le Scrabble est joué, de toute façon.) Avec cette hypothèse implicite, vous êtes sur la bonne voie mais vous devez modifier l'algorithme: vous ne devez pas répéter le calcul pour les mots du dictionnaire qui sont des permutations les uns des autres. Par exemple, vous ne devez pas soustraire à la fois t_ {stop} et t_ {post} dans votre formule. (Il s'agit d'une modification facile à mettre en œuvre.)
whuber