Probabilidade de não desenhar uma palavra de um saco de letras no Scrabble

27

Suponha que você tenha uma sacola com ladrilhos, cada uma com uma letra. Existem blocos com a letra 'A', com 'B' e assim por diante, e 'curinga' (temos ). Suponha que você tenha um dicionário com um número finito de palavras. Você escolhe ladrilhos da sacola sem reposição. Como você calcula (ou estima) a probabilidade de formar zero palavras no dicionário, considerando os blocos selecionados?nn B n n = n A + n B + + n Z + n k knAnBnn=nA+nB++nZ+nkk

Para aqueles que não estão familiarizados com o Scrabble (TM), o caractere curinga pode ser usado para corresponder a qualquer letra. Assim, a palavra [ BOOT ] pode ser 'soletrada' com os blocos 'B', '*', 'O', 'T'.

Para se ter uma idéia da escala do problema, é pequeno, como 7, é de cerca de 100 e o dicionário contém cerca de 100.000 palavras de tamanho ou menor.n kknk

edit: Por 'formar uma palavra', quero dizer uma palavra de comprimento não superior a . Assim, se a palavra [ A ] estiver no dicionário, então, tirando um único 'A' da sacola, a pessoa 'formará uma palavra'. O problema dos curingas é radicalmente simplificado se alguém puder assumir que há palavras com tamanho 1 no dicionário. Pois, se houver, qualquer empate de um curinga pode corresponder automaticamente a uma palavra de comprimento 1 e, portanto, é possível se concentrar no caso em que não há curingas. Portanto, a forma mais escorregadia do problema não possui palavras com uma letra no dicionário.k

Além disso, devo declarar explicitamente que a ordem em que as cartas são retiradas da sacola é irrelevante. Não é necessário desenhar as letras na ordem 'correta' da palavra.

shabbychef
fonte
Não deveria ser 'escolher k ladrilhos sem substituição'? Pergunta muito interessante.
oops. de fato deveria.
shabbychef
Tanto quanto eu me lembro que Scrabble não permitem palavras da letra, então pelo menos que parte do problema é resolvido;)
nico
1
@nico bom ponto, mas acho que isso é apenas para o meio do jogo. As palavras de uma letra não exigem que uma delas seja reproduzida ou permitiriam que uma única letra fosse colocada em qualquer lugar do quadro, ambas claramente inaceitáveis. No entanto, eu estava pensando no movimento de abertura. De fato, a pergunta pode ser declarada de maneira compacta, para aqueles familiarizados com o Scrabble, como "qual é a probabilidade de o primeiro jogador ter que passar?"
shabbychef
@nico Obrigado por esse esclarecimento. Teoricamente, uma questão semelhante se aplica a dicionários que contêm todas as combinações possíveis de duas letras como palavras: quando esse é o caso, qualquer mão de 2 ou mais letras contém automaticamente uma palavra. O comentário de @ shabbychef sobre o meio do jogo mostra como a pergunta original é irrelevante para a maior parte do Scrabble, porque no meio do jogo você tem disponível uma variedade de partes de palavras (prefixos, sufixos e até seções do meio), além das 7 letras do seu mão. Isso aumenta muito as chances de conseguir fazer uma palavra.
whuber

Respostas:

14

Este é um comentário (longo!) Sobre o bom trabalho que o @vqv postou neste tópico. O objetivo é obter uma resposta definitiva. Ele fez o trabalho duro de simplificar o dicionário. Tudo o que resta é explorá-lo ao máximo. Seus resultados sugerem que uma solução de força bruta é viável . Afinal, incluindo um curinga, existem no máximo palavras que se pode fazer com 7 caracteres e parece que menos de 1/10000 deles - digamos, cerca de um milhão - não incluirão algumas informações válidas. palavra. 277=10,460,353,203

A primeira etapa é aumentar o dicionário mínimo com um caractere curinga, "?". 22 das letras aparecem em palavras de duas letras (todas, exceto c, q, v, z). Coloque um curinga nas 22 letras e adicione-o ao dicionário: {a ?, b ?, d ?, ..., y?} Estão agora. Da mesma forma, podemos inspecionar as palavras mínimas de três letras, causando algumas palavras adicionais para aparecer no dicionário. Por fim, adicionamos "??" para o dicionário. Após remover as repetições resultantes, ele contém 342 palavras mínimas.

Uma maneira elegante de proceder - uma que realmente use uma quantidade muito pequena de codificação - é ver esse problema como um problema algébrico . Uma palavra, considerada como um conjunto não ordenado de letras, é apenas um monômio. Por exemplo, "spats" é o monomial . O dicionário, portanto, é uma coleção de monômios. Pareceaps2t

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

(onde, para evitar confusão, escrevi para o caractere curinga).ψ

Um rack contém uma palavra válida se e somente se essa palavra divide o rack.

Uma maneira mais abstrata, mas extremamente poderosa, de dizer isso é que o dicionário gera um ideal no anel polinomial e que os racks possuem valores válidos. as palavras se tornam zero no anel de quociente , enquanto racks sem palavras válidas permanecem diferentes de zero no quociente. Se formarmos a soma de todos os racks em e computá-lo nesse anel de quociente, o número de racks sem palavras será igual ao número de monômios distintos no quociente.R = Z [ a , b , , z , ψ ] R / I RIR=Z[a,b,,z,ψ]R/IR

Além disso, a soma de todos os racks em é fácil de expressar. Seja a soma de todas as letras do alfabeto. contém um monomial para cada rack. (Como um bônus adicional, seus coeficientes contam o número de maneiras que cada rack pode ser formado, permitindo calcular sua probabilidade, se quisermos.)α = a + b + + z + ψ α 7Rα=a+b++z+ψα7

Como um exemplo simples (para ver como isso funciona), suponha que (a) não usamos caracteres curinga e (b) todas as letras de "a" a "x" sejam consideradas palavras. Então, os únicos racks possíveis dos quais as palavras não podem ser formadas devem consistir inteiramente de y e z. Calculamos módulo o ideal gerado por um passo de cada vez, assim: { a , b , c , , x }α=(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.

Podemos ler a chance de obter um rack que não seja uma palavra da resposta final, : cada coeficiente conta as maneiras pelas quais o rack correspondente pode ser desenhado. Por exemplo, existem 21 (de 26 ^ 7 possíveis) maneiras de desenhar 2 y e 5 z porque o coeficiente de é igual a 21.y7+7y6z+21y5z2+35y4z3+35y3z4+21y2z5+7yz6+z7y2z5

A partir de cálculos elementares, é óbvio que esta é a resposta correta. O ponto principal é que esse procedimento funciona independentemente do conteúdo do dicionário.

Observe como reduzir o módulo de potência o ideal em cada estágio reduz o cálculo: esse é o atalho revelado por essa abordagem. (Fim do exemplo.)

Os sistemas de álgebra polinomial implementam esses cálculos . Por exemplo, aqui está o código do 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]

(O dicionário pode ser construído de maneira direta a partir do min.dict de @ vqv; coloquei uma linha aqui mostrando que é curto o suficiente para ser especificado diretamente, se você preferir.)

A saída - que leva dez minutos de computação - é 577958. ( NB Em uma versão anterior desta mensagem, cometi um pequeno erro na preparação do dicionário e obtive 577940. Editei o texto para refletir o que espero que esteja agora os resultados corretos!) Um pouco menos do que o milhão que eu esperava, mas da mesma ordem de magnitude.

Para calcular a chance de obter esse rack, precisamos levar em consideração o número de maneiras pelas quais o rack pode ser desenhado. Como vimos no exemplo, isso é igual ao seu coeficiente em . A chance de desenhar algum rack é a soma de todos esses coeficientes, facilmente encontrados ao definir todas as letras iguais a 1:α7

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

A resposta é igual a 1066056120, dando uma chance de 10,1914% de desenhar um rack do qual nenhuma palavra válida pode ser formada (se todas as letras forem igualmente prováveis).

Quando as probabilidades das letras variarem, substitua cada letra pela chance de ser sorteada:

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)

O resultado é 1.079877553303%, a resposta exata (embora usando um modelo aproximado, desenhando com substituição). Olhando para trás, foram necessárias quatro linhas para inserir os dados (alfabeto, dicionário e frequências do alfabeto) e apenas três linhas para executar o trabalho: descrever como obter a próxima potência de modulo , tomar a 7ª potência recursivamente e substituir as probabilidades para as letras.αI

whuber
fonte
+1 Juntar o léxico e depois minimizá-lo é uma idéia inteligente. A álgebra está além de mim, mas parece que você está calculando uma probabilidade multinomial, e não hipergeométrica. Portanto, a probabilidade é de amostragem com substituição. Eu acho que isso explica por que sua resposta de 1,08% é muito maior do que minha estimativa de 0,4%. Existe uma maneira de modificar sua abordagem para lidar com a amostragem sem substituição?
vqv
2
@vqv Sim. Agora que temos uma lista de meio milhão de racks sem palavras, é simples (alterando as duas últimas linhas de código) calcular a chance de cada rack (sem substituição) e obter o resultado hipergeométrico. A resposta exata é igual a 349870667877/80678106432000 = 0,43366% . Com N = 100K ensaios, seu SE é de 0,021%; portanto, sua resposta deve ter ficado entre 0,38% e 0,49% (IC de 99% dos dois lados). Estou tão feliz que nossas respostas concordam!
whuber
@whuber Você poderia executar o cálculo usando a distribuição de blocos Words With Friends (WWF)? Minha estimativa de 0,4% é baseada no léxico e na distribuição de ladrilhos do WWF. Acho que você está usando a distribuição de blocos Scrabble com o léxico da WWF.
vqv
Opa A resposta exata é 349870675899 (estava com 8022 de folga devido a um erro no meu dicionário.) Isso não faz nenhuma diferença prática, felizmente.
whuber
@vqv Não estou familiarizado com as várias distribuições de blocos. Copiei o meu diretamente do seu código (e usei o seu dicionário) :-). Se você quer dizer a distribuição em osxreality.com/2010/01/01/… , obtenho 1,15444% (com substituição), 0,43366% (sem substituição). O segundo número, na verdade, difere das frequências de Scrabble na 8ª figura significativa.
whuber
14

É muito difícil desenhar um rack que não contenha nenhuma palavra válida no Scrabble e suas variantes. Abaixo está um programa R que escrevi para estimar a probabilidade de o rack inicial de 7 blocos não conter uma palavra válida. Ele usa uma abordagem de monte carlo e o léxico Words With Friends (não consegui encontrar o léxico oficial do Scrabble em um formato fácil). Cada tentativa consiste em desenhar um rack de 7 blocos e verificar se o rack contém uma palavra válida.

Palavras mínimas

Você não precisa digitalizar o léxico inteiro para verificar se o rack contém uma palavra válida. Você só precisa digitalizar um léxico mínimo composto por palavras mínimas . Uma palavra é mínima se não contiver outra palavra como subconjunto. Por exemplo, 'em' é uma palavra mínima; 'vazio' não é. O ponto disso é que, se um rack contém a palavra x , também deve conter qualquer subconjunto de x . Em outras palavras: um rack não contém palavras se não contiver palavras mínimas. Felizmente, a maioria das palavras no léxico não é mínima, portanto elas podem ser eliminadas. Você também pode mesclar palavras equivalentes à permutação. Consegui reduzir o léxico Words With Friends de 172.820 para 201 palavras mínimas.

Os curingas podem ser facilmente manipulados tratando racks e palavras como distribuições nas letras. Verificamos se um rack contém uma palavra subtraindo uma distribuição da outra. Isso nos dá o número de cada letra que falta no rack. Se a soma desses números for o número de curingas, a palavra estará no rack.

O único problema com a abordagem de Monte Carlo é que o evento em que estamos interessados ​​é muito raro. Portanto, são necessárias muitas e muitas tentativas para obter uma estimativa com um erro padrão pequeno o suficiente. Executei meu programa (colado na parte inferior) com tentativas e obtive uma probabilidade estimada de 0,004 de que o rack inicial não contenha uma palavra válida . O erro padrão estimado dessa estimativa é 0,0002. Demorou apenas alguns minutos para rodar no meu Mac Pro, incluindo o download do léxico.N=100,000

Eu estaria interessado em ver se alguém pode criar um algoritmo exato eficiente. Uma abordagem ingênua baseada na inclusão-exclusão parece envolver uma explosão combinatória.

Inclusão-exclusão

Eu acho que essa é uma solução ruim, mas aqui está um esboço incompleto. Em princípio, você pode escrever um programa para fazer o cálculo, mas a especificação seria tortuosa.

A probabilidade que queremos calcular é O evento dentro da probabilidade no lado direito é uma união de eventos: onde é um léxico mínimo. Podemos expandi-lo usando a fórmula de inclusão-exclusão. Envolve considerar todas as interseções possíveis dos eventos acima. Vamos denotam o conjunto das partes de , ou seja, o conjunto de todos os subconjuntos possíveis de . Então

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

A última coisa a especificar é como calcular a probabilidade na última linha acima. Envolve uma hipergeometria multivariada. é o evento que o rack contém cada palavra . É difícil lidar com isso por causa dos curingas. Por condicionamento, teremos que considerar cada um dos seguintes casos: o rack não contém curingas, o rack contém 1 curinga, o rack contém 2 curingas, ...

xS{k-tile rack contains x}
S

Então

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

Vou parar por aqui, porque as expansões são tortuosas para escrever e nem um pouco esclarecedoras. É mais fácil escrever um programa de computador para fazer isso. Mas agora você deve ver que a abordagem de inclusão-exclusão é intratável. Envolve termos, cada um dos quais também é muito complicado. Para o léxico, considerei acima .2|M|2|M|3.2×1060

Digitalizando todos os racks possíveis

Eu acho que isso é computacionalmente mais fácil, porque há menos racks possíveis do que possíveis subconjuntos de palavras mínimas. Reduzimos sucessivamente o conjunto de possíveisk- prateleiras de ladrilhos até obtermos o conjunto de prateleiras que não contêm palavras. Para Scrabble (ou Words With Friends), o número possível de racks de 7 blocos é de dezenas de bilhões. Contar o número daqueles que não contêm uma palavra possível deve ser possível com algumas dezenas de linhas de código R. Mas acho que você deve ser capaz de fazer melhor do que apenas enumerar todos os racks possíveis. Por exemplo, 'aa' é uma palavra mínima. Isso elimina imediatamente todos os racks que contêm mais de um 'a'. Você pode repetir com outras palavras. A memória não deve ser um problema para computadores modernos. Um rack Scrabble de 7 blocos requer menos de 7 bytes de armazenamento. Na pior das hipóteses, usaríamos alguns gigabytes para armazenar todos os racks possíveis, mas também não acho que seja uma boa ideia. Alguém pode querer pensar mais sobre isso.

Programa 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
fonte
Uau ... muito bom acompanhamento.
Matt Parker
Estou um pouco surpreso que tenha reduzido para 201 palavras. Embora para a primeira palavra reproduzida, as regras da nossa casa aceitam 'I' e 'A' como palavras, o que provavelmente reduziria ainda mais o número mínimo de palavras. Eu estava esperando para ver alguém busto a análise inclusão-exclusão, que deve ser bastante peludo ...
shabbychef
@shabbychef Não há palavras com uma letra no léxico. A maioria das palavras mínimas são de 2 e 3 letras. Aqui está a distribuição completa dos comprimentos mínimos de palavras: 2: 73, 3:86, 4:31, 5: 9, 6: 2. As palavras de 6 letras são: GLYCYL e SYZYGY.
vqv
@shabbychef Atualizei minha resposta para incluir um esboço de uma abordagem exata de inclusão-exclusão. É pior que cabeludo.
vqv
Ótimo trabalho! Eu amo que essa pergunta, que poderia ser colocada como uma frase (para aqueles com experiência suficiente), tenha revelado monte carlo, inclusão-exclusão, DAGs, pesquisa de árvores, álgebra polinomial e que suas simulações são confirmadas pelo teórico de @ whuber. Felicidades!
shabbychef
7

Srikant está certo: um estudo de Monte Carlo é o caminho a percorrer. Existem duas razões. Primeiro, a resposta depende fortemente da estrutura do dicionário. Dois extremos são: (1) o dicionário contém todas as palavras possíveis de uma única letra. Nesse caso, a chance de não formar uma palavra em um empate de ou mais letras é zero. (2) O dicionário contém apenas palavras formadas em uma única letra ( por exemplo , "a", "aa", "aaa", etc. ) A chance de não formar uma palavra com um letras é facilmente determinada e obviamente é diferente de zero. Qualquer resposta definitiva em formato fechado teria que incorporar toda a estrutura do dicionário e seria uma fórmula realmente terrível e longa.1k

A segunda razão é que o MC é realmente viável: você só precisa fazer o que é certo. O parágrafo anterior fornece uma pista: não apenas gere palavras aleatoriamente e procure-as; em vez disso, analise o dicionário primeiro e explore sua estrutura.

Uma maneira representa as palavras no dicionário como uma árvore. A árvore está enraizada no símbolo vazio e se ramifica em cada letra até o fim; suas folhas são (é claro) as próprias palavras. No entanto, também podemos inserir todas as permutações não triviais de cada palavra na árvore também (até delas para cada palavra). Isso pode ser feito com eficiência, porque não é necessário armazenar todas essas permutações; somente as arestas da árvore precisam ser adicionadas. As folhas permanecem as mesmas. De fato, isso pode ser simplificado ainda mais, insistindo que a árvore seja seguida em ordem alfabética .k!1

Em outras palavras, para determinar se um conjunto múltiplo de caracteres está no dicionário, primeiro organize os elementos na ordem de classificação,kem seguida, procure essa "palavra" classificada em uma árvore construída a partir dos representantes classificados das palavras no dicionário original. Na verdade, ele será menor que a árvore original porque mescla todos os conjuntos de palavras equivalentes à classificação, como {stop, post, pots, opts, spot}. De fato, em um dicionário em inglês, essa classe de palavras nunca seria alcançada, porque "so" seria encontrado primeiro. Vamos ver isso em ação. O multiset classificado é "opst"; o "o" ramifica para todas as palavras que contêm apenas as letras {o, p, ..., z}, o "p" ramifica para todas as palavras que contêm apenas {o, p, ..., z} e no máximo um "o" e, finalmente, o "s" se ramifica para a folha "so"! (Presumi que nenhum dos candidatos plausíveis "o", "op", "

É necessária uma modificação para lidar com curingas: deixarei que os tipos de programadores entre vocês pensem sobre isso. Não aumentará o tamanho do dicionário (deve diminuir, de fato); desacelerará um pouco a travessia da árvore, mas sem alterá-la de maneira fundamental. Em qualquer dicionário que contenha uma palavra de uma letra, como inglês ("a", "i"), não há complicações: a presença de um curinga significa que você pode formar uma palavra! (Isso sugere que a pergunta original pode não ser tão interessante quanto parece.)

O resultado é que uma única pesquisa no dicionário requer (a) a classificação de um conjunto múltiplo de letras e (b) a travessia de não mais do que arestas de uma árvore. O tempo de execução é . Se você habilmente gerar multisets aleatórios em ordem classificada (posso pensar em várias maneiras eficientes de fazer isso), o tempo de execução será reduzido para . Multiplique isso pelo número de iterações para obter o tempo total de execução.k O ( k log ( k ) ) O ( k )kkO(klog(k))O(k)

Aposto que você poderia conduzir este estudo com um conjunto real de Scrabble e um milhão de iterações em questão de segundos.

whuber
fonte
@whuber A árvore é uma ideia interessante (votada anteriormente para essa ideia), mas não exigiria muita memória? Acho que depende da diversidade do dicionário, mas acho que um dicionário razoavelmente diverso exigiria muitas árvores. Por exemplo, a árvore 'b' começaria com a letra 'b' em vez de 'a' para todas as palavras que não tem 'a' neles. Da mesma forma, a árvore 'c' começaria com a letra 'c' para aquelas palavras que não possuem 'a' e 'b', mas possuem 'c'. Minha abordagem direta proposta parece mais simples, pois requer uma passagem única de todas as palavras do dicionário, não?
1
@ Krikant: A árvore provavelmente exigiria muito menos RAM do que o cache de todo o dicionário para começar. Você está realmente preocupado com alguns megabytes de RAM, afinal? Aliás, há apenas uma árvore, não muitas: todas estão enraizadas na palavra vazia. Sua abordagem, como eu a entendi, requer várias pesquisas no dicionário (até 7! Delas ) em cada iteração , tornando-o impraticável como o medo de @shabbychef. Ajudaria se você pudesse elaborar o algoritmo que tem em mente onde escreve "veja se consegue formar uma palavra": isso oculta muitos detalhes importantes!
whuber
@ whuber: eu percebi o fato de que existe apenas uma árvore depois que postei meu comentário. De acordo com minha abordagem - concordo que minha proposta de monte carlo é imprecisa e sua resposta mostra como é possível implementar o monte carlo nesse cenário. Na verdade, eu quis dizer que a abordagem direta (veja minha resposta) pode ser realmente mais simples, pois exige uma operação única no dicionário, ao contrário de um monte carlo, que requer vários milhares de iterações na árvore. Apenas pensando nos méritos relativos das abordagens.
@ Krikant Abstive-me de comentar sua abordagem direta porque suspeito que receba as respostas erradas. Parece não dar conta da estrutura do dicionário: ou seja, os relacionamentos dos subconjuntos entre as palavras. Por exemplo, sua fórmula obteria a resposta correta de zero para todos os dicionários que contêm todas as palavras possíveis de uma letra?
whuber
@whuber hmmm bom ponto. Talvez eu esteja respondendo à pergunta errada!
2

Abordagem Monte Carlo

A abordagem rápida e suja é fazer um estudo de Monte Carlo. Desenhe ladrilhos vezes e, para cada desenho de ladrilhos, veja se é possível formar uma palavra. Indique o número de vezes que você pode formar uma palavra por . A probabilidade desejada seria:m k m wkmkmw

1mwm

Abordagem direta

Deixe o número de palavras no dicionário ser dado por . Seja o número de maneiras pelas quais podemos formar a palavra . Deixe o número de letras necessário para a palavra ser indicado por (ou seja, a palavra precisa de número de letras 'a' etc). Denotar o número de palavras que pode formar com todas as peças por .t s s ° s th m um , m b , . . . , m zStssthsthma,mb,...,mz m um NsthmaN

N=(nk)

e

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

(Incluir o impacto dos blocos curinga é um pouco mais complicado. Adiaremos esse problema por enquanto.)

Assim, a probabilidade desejada é:

1stsN

fonte
A abordagem rápida e suja pode não ser tão rápida! O dicionário pode conter 100.000 palavras e a busca por uma correspondência dos blocos fornecidos pode ser um desastre de codificação.
shabbychef
@shabbychef Isso é algo bem feito para se adequar aos corretores ortográficos. Veja, por exemplo, n3labs.com/pdf/lexicon-squeeze.pdf
@shabbychef Reg monte-carlo- se o dicionário for classificado, uma correspondência deve ser bastante rápida, não? De qualquer forma, a abordagem direta que descrevi anteriormente era falha. Eu consertei isso. O problema na minha solução anterior era que a mesma palavra pode ser formada de várias maneiras (por exemplo, 'bat', 'b * t' etc.).
1
@shabbychef Em uma reflexão mais aprofundada, concordo com você que a abordagem de Monte Carlo não funcionará. Uma questão é que você precisa descobrir quais palavras você pode realmente formar com os blocos k e a segunda é que você pode formar várias palavras com os blocos k. Calcular essas combinações a partir de k ladrilhos provavelmente não é tão fácil.
1
@ Obrigado Krikant. Sua fórmula parece assumir que você precisa usar todas as letras k para formar a palavra, mas não acho que seja isso que o OP esteja pedindo. (Não é assim que o Scrabble é reproduzido.) Com essa suposição implícita, você está no caminho certo, mas precisa modificar o algoritmo: não deve repetir o cálculo das palavras no dicionário que são permutações uma da outra. Por exemplo, você não deve subtrair t_ {stop} e t_ {post} na sua fórmula. (Esta é uma modificação fácil de implementar.)
whuber