Prawdopodobieństwo, że nie narysuje słowa z worka liter w Scrabble

27

Załóżmy, że masz torbę z płytkami, z których każda zawiera literę. Są kafelki z literą „A”, z „B” itd., I „symbole wieloznaczne” (mamy ). Załóżmy, że masz słownik ze skończoną liczbą słów. Z torby wybierasz płytek bez wymiany. Jak obliczysz (lub oszacujesz) prawdopodobieństwo, że możesz sformułować zero słów ze słownika, biorąc pod uwagę wybrane płytek?n A n B n n = n A + n B + + n Z + n k knnAnBnn=nA+nB++nZ+nkk

W przypadku osób niezaznajomionych ze Scrabble (TM) można użyć znaku zastępczego, aby dopasować dowolną literę. Zatem słowo [ BOOT ] może być „ortograficzne” z kafelkami „B”, „*”, „O”, „T”.

Aby dać wyobrażenie o skali problemu, jest małe, na przykład 7, wynosi około 100, a słownik zawiera około 100 000 słów o wielkości lub mniejszej.n kknk

edytuj: Przez „uformuj słowo” mam na myśli słowo o długości nie większej niż . Tak więc, jeśli słowo [ A ] znajduje się w słowniku, to poprzez wyciągnięcie nawet jednego „A” z torby, „uformowano słowo”. Problem symboli wieloznacznych jest radykalnie uproszczony, jeśli można założyć, że w słowniku znajdują się słowa o długości 1. Jeśli tak, każde losowanie symbolu wieloznacznego może automatycznie dopasować długość 1 słowa, a zatem można skoncentrować się na przypadku, w którym nie ma symboli wieloznacznych. Tak więc bardziej śliska forma problemu nie zawiera słów 1-literowych w słowniku.k

Powinienem również wyraźnie stwierdzić, że kolejność, w jakiej litery są wyciągane z torby, jest nieistotna. Nie trzeba rysować liter w „poprawnej” kolejności słowa.

shabbychef
źródło
Czy nie powinno to być „wybieranie k płytek bez wymiany”? Bardzo interesujące pytanie.
ups. rzeczywiście powinno.
shabbychef
O ile pamiętam, Scrabble nie pozwala na użycie jednej litery słowa, więc przynajmniej ta część problemu została rozwiązana;)
nico
1
@nico dobra uwaga, ale myślę, że dotyczy to tylko środkowej fazy gry. 1-literowe słowa albo nie wymagają zagrania jednej litery, albo pozwolą umieścić jedną literę w dowolnym miejscu na planszy, oba wyraźnie niedopuszczalne. Myślałem jednak o ruchu otwierającym. W rzeczywistości, dla osób zaznajomionych ze Scrabble, pytanie może być zwięźle sformułowane jako „jakie jest prawdopodobieństwo, że pierwszy gracz będzie musiał spasować?”
shabbychef
@nico Dziękuję za to wyjaśnienie. Teoretycznie podobna kwestia dotyczy słowników zawierających wszystkie możliwe kombinacje dwuliterowe jako słowa: w takim przypadku każda ręka składająca się z dwóch lub więcej liter automatycznie zawiera słowo. Komentarz @ shabbychef o środkowej fazie gry pokazuje, jak nieistotne jest pierwotne pytanie dla większości Scrabble, ponieważ w środkowej fazie gry masz do dyspozycji szereg części słów (przedrostki, przyrostki, a nawet środkowe sekcje) oprócz 7 liter w twoim dłoń. To znacznie zwiększa szanse na słowo.
whuber

Odpowiedzi:

14

To jest (długi!) Komentarz do dobrej pracy opublikowanej przez @vqv w tym wątku. Ma na celu uzyskanie ostatecznej odpowiedzi. Ciężko pracował nad uproszczeniem słownika. Pozostaje tylko wykorzystać go w pełni. Jego wyniki sugerują, że możliwe jest rozwiązanie z użyciem siły brutalnej . W końcu, włączając w to symbol wieloznaczny, istnieje co najwyżej słów, które można sformułować za pomocą 7 znaków, i wygląda na to, że mniej niż 1/10000 z nich - powiedzmy, około miliona - nie będzie zawierać niektórych poprawnych słowo. 277=10,460,353,203

Pierwszym krokiem jest uzupełnienie minimalnego słownika znakiem wieloznacznym „?”. 22 litery pojawiają się w dwuliterowych słowach (wszystkie oprócz c, q, v, z). Dołącz znak wieloznaczny do tych 22 liter i dodaj je do słownika: {a ?, b ?, d ?, ..., y?} Już są. Podobnie możemy sprawdzić minimalne trzyliterowe słowa, powodując dodatkowe słowa pojawić się w słowniku. Na koniec dodajemy „??” do słownika. Po usunięciu powtórzeń zawiera 342 minimalne słowa.

Elegancki sposób postępowania - taki, który używa bardzo niewielkiej ilości kodowania - polega na postrzeganiu tego problemu jako algebraicznego . Słowo, uważane za nieuporządkowany zestaw liter, jest po prostu monomialne. Na przykład „spats” to monomialne . Słownik jest zatem zbiorem monomialów. To wygląda jakaps2t

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

(gdzie, aby uniknąć zamieszania, napisałem dla znaku wieloznacznego).ψ

Stojak zawiera prawidłowe słowo, tylko wtedy, gdy to słowo dzieli stojak.

Bardziej abstrakcyjnym, ale niezwykle potężnym sposobem na powiedzenie tego jest to, że słownik generuje idealne w pierścieniu wielomianowym i że stojaki z poprawnymi słowa stają się zerowe w pierścieniu ilorazowym , natomiast stojaki bez prawidłowych słów pozostają niezerowe w ilorazie. Jeśli utworzymy sumę wszystkich stojaków w i obliczymy je w tym pierścieniu ilorazowym, wówczas liczba stojaków bez słów jest równa liczbie różnych jednomianów w ilorazie.R = Z [ a , b , , z , ψ ] R / I RIR=Z[a,b,,z,ψ]R/IR

Ponadto suma wszystkich stojaków w jest łatwa do wyrażenia. Niech będzie sumą wszystkich liter alfabetu. zawiera jeden monomial na każdy stojak. (Jako dodatkowy bonus, jego współczynniki liczą liczbę sposobów, w jakie można utworzyć każdy stojak, co pozwala nam obliczyć jego prawdopodobieństwo, jeśli chcemy.)α = a + b + + z + ψ α 7Rα=a+b++z+ψα7

Jako prosty przykład (aby zobaczyć, jak to działa) załóżmy, że (a) nie używamy symboli wieloznacznych i (b) wszystkie litery od „a” do „x” są uważane za słowa. Zatem jedyne możliwe stojaki, z których nie można utworzyć słów, muszą składać się wyłącznie z liter y i z. Obliczamy modulo ideału generowanego przez krok po kroku, w ten sposób: { 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.

Z ostatecznej odpowiedzi możemy odczytać szansę otrzymania stojaka bez słów, : każdy współczynnik zlicza sposoby, w jakie można narysować odpowiedni stojak. Na przykład istnieje 21 (z 26 ^ 7 możliwych) sposobów na narysowanie 2 lat i 5 z, ponieważ współczynnik wynosi 21.y7+7y6z+21y5z2+35y4z3+35y3z4+21y2z5+7yz6+z7y2z5

Z elementarnych obliczeń wynika, że ​​jest to poprawna odpowiedź. Chodzi o to, że ta procedura działa niezależnie od zawartości słownika.

Zauważ, jak redukcja modułu mocy ideału na każdym etapie zmniejsza obliczenia: oto skrót ujawniony w tym podejściu. (Koniec przykładu.)

Systemy algebry wielomianowej realizują te obliczenia . Na przykład, oto kod 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]

(Słownik można zbudować w prosty sposób z min.dict @ vqv; wstawiłem tutaj wiersz pokazujący, że jest on wystarczająco krótki, aby można go było podać bezpośrednio, jeśli chcesz).

Wynik - który zajmuje dziesięć minut obliczeń - wynosi 577958. ( Uwaga: We wcześniejszej wersji tego komunikatu popełniłem niewielki błąd podczas przygotowywania słownika i otrzymałem 577940. Edytowałem tekst, aby odzwierciedlić to, co mam nadzieję teraz poprawne wyniki!) Nieco mniej niż milion oczekiwałem, ale tego samego rzędu wielkości.

Aby obliczyć szansę na uzyskanie takiego stojaka, musimy wziąć pod uwagę liczbę sposobów, w jakie można go wyciągnąć. Jak widzieliśmy w przykładzie, jest to równe jego współczynnikowi w . Szansa rysunek jakiś taki stojak jest sumą wszystkich tych współczynników, łatwo znaleźć poprzez ustawienie wszystkich liter równy 1:α7

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

Odpowiedź równa się 1066056120, co daje 10,1914% szansy na wyciągnięcie stojaka, z którego nie można utworzyć prawidłowego słowa (jeśli wszystkie litery są jednakowo prawdopodobne).

Gdy prawdopodobieństwa liter są różne, po prostu zamień każdą literę na szansę na narysowanie:

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)

Wynik wynosi 1.079877553303%, dokładna odpowiedź (choć przy użyciu modelu przybliżonego, rysunek z zamiennikiem). Patrząc wstecz, dane zajęły cztery linie (alfabet, słownik i częstotliwości alfabetu) i tylko trzy linie do wykonania pracy: opisz, jak pobrać następną potęgę modulo , rekurencyjnie weź siódmą potęgę i zamień ją prawdopodobieństwa liter.αI

Whuber
źródło
+1 Przyłączenie do leksykonu, a następnie ponowne zminimalizowanie go to sprytny pomysł. Algebra jest poza mną, ale wydaje się, że obliczasz prawdopodobieństwo wielomianowe, a nie hipergeometryczne. Prawdopodobieństwo dotyczy próbkowania z wymianą. Myślę, że to wyjaśnia, dlaczego twoja odpowiedź w wysokości 1,08% jest o wiele większa niż moje szacunki na 0,4%. Czy istnieje sposób zmodyfikowania podejścia do obsługi próbkowania bez wymiany?
vqv 10.01.11
2
@vqv Tak. Teraz, gdy mamy listę około pół miliona szaf bez słów, proste (poprzez zmianę dwóch ostatnich wierszy kodu) jest obliczenie szansy dla każdej szafy (bez wymiany) i uzyskanie wyniku hipergeometrycznego. Dokładna odpowiedź wynosi 349870667877/80678106432000 = 0,43366% . Przy próbach N = 100K twoja SE wynosi 0,021%, więc twoja odpowiedź powinna wynosić od 0,38% do 0,49% (dwustronny 99% CI). Cieszę się, że nasze odpowiedzi się zgadzają!
whuber
@whuber Czy możesz uruchomić obliczenia przy użyciu dystrybucji kafelków Words With Friends (WWF)? Moje oszacowanie na 0,4% oparte jest na leksykonie WWF i rozmieszczeniu płytek WWF. Myślę, że używasz dystrybucji płytek Scrabble z leksykonem WWF.
vqv
Ups Dokładna odpowiedź to w rzeczywistości 349870675899 (miałem 8022 wyłączony z powodu błędu w moim słowniku). Na szczęście nie ma to praktycznej różnicy.
whuber
@vqv Nie znam różnych dystrybucji kafelków. Skopiowałem mój bezpośrednio z twojego kodu (i użyłem twojego słownika) :-). Jeśli masz na myśli rozkład na osxreality.com/2010/01/01/... , to otrzymuję 1,15444% (z wymianą), 0,43366% (bez wymiany). Druga liczba faktycznie różni się od częstotliwości Scrabble na ósmej znaczącej liczbie.
whuber
14

Bardzo trudno jest narysować stojak, który nie zawiera żadnego poprawnego słowa w Scrabble i jego wariantach. Poniżej znajduje się program R, który napisałem w celu oszacowania prawdopodobieństwa, że ​​początkowy 7-kafelkowy stojak nie zawiera poprawnego słowa. Wykorzystuje podejście Monte Carlo i leksykon Words With Friends (nie mogłem znaleźć oficjalnego leksykonu Scrabble w łatwym formacie). Każda próba polega na narysowaniu 7-kafelkowego stojaka, a następnie sprawdzeniu, czy stojak zawiera prawidłowe słowo.

Minimalne słowa

Nie musisz skanować całego leksykonu, aby sprawdzić, czy stojak zawiera prawidłowe słowo. Wystarczy zeskanować minimalny leksykon składający się z minimalnej liczby słów. Słowo jest minimalne, jeśli nie zawiera innego słowa jako podzestawu. Na przykład „em” to minimalne słowo; „pusty” nie jest. Chodzi o to, że jeśli stojak zawiera słowo x, to musi również zawierać dowolny podzbiór x . Innymi słowy: stojak nie zawiera słów iff nie zawiera minimalnych słów. Na szczęście większość słów w leksykonie nie jest minimalna, więc można je wyeliminować. Możesz także łączyć słowa równoważne permutacji. Udało mi się zmniejszyć leksykon Words With Friends z 172 820 do 201 minimalnych słów.

Symbole wieloznaczne można łatwo obsługiwać, traktując stojaki i słowa jako rozkład na litery. Sprawdzamy, czy stojak zawiera słowo, odejmując jedną dystrybucję od drugiej. Daje nam to numer każdej brakującej litery w stojaku. Jeśli suma tych liczb jest liczbą symboli wieloznacznych, to słowo znajduje się w szafie.

Jedynym problemem związanym z podejściem monte carlo jest to, że wydarzenie, które nas interesuje, jest bardzo rzadkie. Dlatego oszacowanie przy wystarczająco małym błędzie standardowym powinno zająć wiele, wiele prób. Uruchomiłem mój program (wklejony na dole) z prób i uzyskałem szacunkowe prawdopodobieństwo 0,004, że początkowy stojak nie zawiera poprawnego słowa . Szacowany błąd standardowy tego oszacowania wynosi 0,0002. Uruchomienie mojego komputera Mac Pro zajęło zaledwie kilka minut, w tym pobranie leksykonu.N=100,000

Chciałbym sprawdzić, czy ktoś może wymyślić skuteczny algorytm dokładny. Wydaje się, że naiwne podejście oparte na wykluczeniu włączenia mogłoby obejmować wybuch kombinatoryczny.

Włączenie-wykluczenie

Myślę, że to złe rozwiązanie, ale tutaj i tak jest niepełny szkic. Zasadniczo możesz napisać program do wykonania obliczeń, ale specyfikacja byłaby skomplikowana.

Prawdopodobieństwo, które chcemy obliczyć, to Zdarzenie wewnątrz prawdopodobieństwa po prawej stronie jest zdarzeń: gdzie jest minimalnym leksykonem. Możemy go rozwinąć, stosując formułę włączenia-wykluczenia. Polega ona na rozważeniu wszystkich możliwych skrzyżowań powyższych wydarzeń. Niech oznacza zbiór mocy , czyli zbiór wszystkich możliwych podzbiorów . Następnie

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

Ostatnią rzeczą do określenia jest sposób obliczenia prawdopodobieństwa w ostatnim wierszu powyżej. Obejmuje wielowymiarową hipergeometrię. jest zdarzeniem, że regał zawiera każde słowo . Jest to ból, z którym trzeba sobie radzić z powodu symboli wieloznacznych. Będziemy musieli rozważyć, kondycjonując, każdy z następujących przypadków: stojak nie zawiera symboli wieloznacznych, stojak zawiera 1 symbol wieloznaczny, stojak zawiera 2 symbole wieloznaczne, ...

xS{k-tile rack contains x}
S

Następnie

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

Zatrzymam się tutaj, ponieważ rozszerzenia są trudne do napisania i wcale nie są pouczające. Aby to zrobić, łatwiej jest napisać program komputerowy. Ale do tej pory powinieneś zobaczyć, że podejście włączenia-wykluczenia jest trudne. Obejmuje warunki, z których każdy jest również bardzo skomplikowany. W przypadku leksykonu rozważałem powyżej .2|M|2|M|3.2×1060

Skanowanie wszystkich możliwych stojaków

Myślę, że jest to obliczeniowo łatwiejsze, ponieważ jest mniej możliwych stojaków niż możliwe podzbiory minimalnych słów. Sukcesywnie zmniejszamy zbiór możliwych wartościk-podstawiać stojaki, dopóki nie otrzymamy zestawu stojaków, które nie zawierają słów. W przypadku Scrabble (lub Words With Friends) liczba możliwych 7-kafelkowych półek wynosi kilkadziesiąt miliardów. Liczenie liczby tych, które nie zawierają możliwego słowa, powinno być wykonalne za pomocą kilkudziesięciu wierszy kodu R. Ale myślę, że powinieneś być w stanie zrobić coś lepszego niż tylko wyliczenie wszystkich możliwych stojaków. Na przykład „aa” to minimalne słowo. To natychmiast eliminuje wszystkie szafy zawierające więcej niż jedno „a”. Możesz powtórzyć innymi słowami. Pamięć nie powinna być problemem dla współczesnych komputerów. 7-kafelkowy stojak Scrabble wymaga mniej niż 7 bajtów pamięci. W najgorszym przypadku wykorzystalibyśmy kilka gigabajtów do przechowywania wszystkich możliwych stojaków, ale nie sądzę, że to też dobry pomysł. Ktoś może chcieć więcej o tym pomyśleć.

Program 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
źródło
Wow ... bardzo miłe kontynuacje.
Matt Parker,
Jestem nieco zaskoczony, że zostało zredukowane do 201 słów. Chociaż w przypadku pierwszego odtworzonego słowa zasady naszego domu przyjmują „I” i „A” jako słowa, co prawdopodobnie jeszcze bardziej zmniejszy liczbę minimalnych słów. Miałem nadzieję, że ktoś wypuści analizę wykluczenia, która powinna być dość owłosiona ...
shabbychef
@shabbychef W leksykonie nie ma 1-literowych słów. Najbardziej minimalnymi słowami są słowa 2- i 3-literowe. Oto pełna dystrybucja minimalnych długości słów: 2: 73, 3:86, 4:31, 5: 9, 6: 2. 6-literowe słowa to: GLYCYL i SYZYGY.
vqv
@shabbychef Zaktualizowałem moją odpowiedź, aby uwzględnić szkic dokładnego podejścia do włączenia / wyłączenia. Jest gorzej niż owłosione.
vqv
świetna robota! Podoba mi się, że to pytanie, które można postawić jako jedno zdanie (do osób o wystarczającym pochodzeniu), wydobyło Monte Carlo, wykluczenie włączenia, DAG, wyszukiwanie drzew, algebrę wielomianową oraz że twoje symulacje są potwierdzone przez teorię @ whuber. Twoje zdrowie!
shabbychef
7

Srikant ma rację: najlepszym rozwiązaniem jest badanie Monte Carlo. Są dwa powody. Po pierwsze, odpowiedź zależy w dużej mierze od struktury słownika. Dwie skrajności to (1), że słownik zawiera każde możliwe jedno literowe słowo. W takim przypadku szansa, że ​​nie utworzy słowa w losowaniu lub więcej liter, wynosi zero. (2) Słownik zawiera tylko słowa utworzone z jednej litery ( np. „A”, „aa”, „aaa” itp .). Szansa, że ​​nie będzie słowa w losowaniu liter, jest łatwa do ustalenia i oczywiście jest niezerowa. Każda określona odpowiedź w formie zamkniętej musiałaby obejmować całą strukturę słownika i byłaby naprawdę okropną i długą formułą.1k

Drugi powód jest taki, że MC rzeczywiście jest wykonalne: musisz po prostu zrobić to dobrze. Poprzedni akapit zawiera wskazówkę: nie generuj słów losowo i sprawdzaj je; zamiast tego najpierw przeanalizuj słownik i wykorzystaj jego strukturę.

Jeden ze sposobów reprezentuje słowa w słowniku jako drzewo. Drzewo jest zakorzenione w pustym symbolu i rozgałęzia się na każdej literze do końca; jego liście to (oczywiście) same słowa. Jednak możemy również wstawić wszystkie nieszablonowe permutacji każdego słowa w drzewo, zbyt (do z nich dla każdego wyrazu). Można to zrobić skutecznie, ponieważ nie trzeba przechowywać wszystkich tych permutacji; należy dodać tylko krawędzie drzewa. Liście pozostają takie same. W rzeczywistości można to jeszcze bardziej uprościć, nalegając, aby drzewo było śledzone w kolejności alfabetycznej .k!1

Innymi słowy, aby ustalić, czy w słowniku znajduje się wielu znaków, najpierw ułóż elementy w posortowanej kolejności,knastępnie poszukaj tego posortowanego „słowa” w drzewie zbudowanym z posortowanych przedstawicieli słów w oryginalnym słowniku. To będzie faktycznie mniejsze niż oryginalne drzewo, ponieważ łączy wszystkie zestawy słów, które są równoważne sortowaniu, takie jak {stop, post, pots, opts, spot}. W słowniku angielskim ta klasa słów i tak nigdy nie byłaby dostępna, ponieważ „tak” byłoby znalezione jako pierwsze. Zobaczmy to w akcji. Posortowany multiset to „opst”; „o” rozgałęzia się na wszystkie słowa zawierające tylko litery {o, p, ..., z}, „p” rozgałęzia się na wszystkie słowa zawierające tylko {o, p, ..., z} i co najwyżej jeden „o”, a na końcu „s” rozgałęzi się do liścia „so”! (Przyjąłem, że żaden z możliwych kandydatów „o”, „op”, „

Potrzebna jest modyfikacja do obsługi symboli wieloznacznych: Pozwolę programistom na zastanowienie się nad tym. Nie zwiększy rozmiaru słownika (powinien go zmniejszyć); nieco spowolni przejście drzewa, ale nie zmieni go w żaden fundamentalny sposób. W każdym słowniku zawierającym jedno litrowe słowo, takim jak angielski („a”, „i”), nie ma komplikacji: obecność znaku wieloznacznego oznacza, że ​​możesz utworzyć słowo! (To sugeruje, że oryginalne pytanie może nie być tak interesujące, jak się wydaje.)

Rezultat jest taki, że wyszukiwanie pojedynczego słownika wymaga (a) sortowania wielisetowego biuletynu i (b) przejścia nie więcej niż krawędzi drzewa. Czas działania to . Jeśli sprytnie wygenerujesz losowe multisety w posortowanej kolejności (mogę wymyślić kilka skutecznych sposobów, aby to zrobić), czas działania zmniejsza się do . Pomnóż to przez liczbę iteracji, aby uzyskać całkowity czas działania.k O ( k log ( k ) ) O ( k )kkO(klog(k))O(k)

Założę się, że możesz przeprowadzić to badanie z prawdziwym zestawem Scrabble i milionem iteracji w ciągu kilku sekund.

Whuber
źródło
@whuber Drzewo to fajny pomysł (głosowanie na ten pomysł), ale czy nie wymagałoby dużo pamięci? Myślę, że to zależy od tego, jak różnorodny jest słownik, ale przypuszczam, że dość zróżnicowany słownik wymagałby wielu drzew. Na przykład drzewo „b” zaczynałoby się od litery „b” zamiast „a” dla wszystkich tych słów, które nie mieć w nich „a”. Podobnie drzewo „c” zaczynałoby się od litery „c” dla tych słów, które nie mają „a” i „b”, ale mają „c”. Moje zaproponowane bezpośrednie podejście wydaje się prostsze, ponieważ wymaga jednorazowego przejścia wszystkich słów w słowniku, prawda?
1
@Sikikant: Drzewo prawdopodobnie wymagałoby o wiele mniej pamięci RAM niż buforowanie całego słownika na początek. Czy tak naprawdę martwisz się kilkoma megabajtami pamięci RAM? BTW, jest tylko jedno drzewo, nie wiele: wszystkie są zakorzenione w pustym słowie. Twoje podejście, tak jak to rozumiem, wymaga wielokrotnego wyszukiwania słownika (do 7!) Na każdej iteracji , co czyni go niepraktycznym, ponieważ obawia się @shabbychef. Byłoby pomocne, gdybyś mógł rozwinąć algorytm, który masz na myśli, gdy piszesz „sprawdź, czy potrafisz sformułować słowo”: kryje w sobie wiele ważnych szczegółów!
whuber
@whuber: Po opublikowaniu komentarza zdałem sobie sprawę, że istnieje tylko jedno drzewo. Reg moje podejście - zgadzam się, że moja propozycja monte carlo jest rozmyta, a twoja odpowiedź wyjaśnia, w jaki sposób można faktycznie wdrożyć monte carlo w tym ustawieniu. Miałem na myśli, że bezpośrednie podejście (patrz moja odpowiedź) może być prostsze, ponieważ takie podejście wymaga jednorazowej operacji na słowniku, w przeciwieństwie do Monte Carlo, które wymaga kilku tysięcy iteracji na drzewie. Zastanawiam się tylko nad względnymi zaletami podejść.
@Sikikant Powstrzymałem się od komentowania twojego bezpośredniego podejścia, ponieważ podejrzewam, że dostaje złe odpowiedzi. Wygląda na to, że nie uwzględnia struktury słownika, to znaczy relacji podzbiorów między słowami. Na przykład, czy Twoja formuła uzyska poprawną odpowiedź na zero dla wszystkich słowników zawierających wszystkie możliwe słowa zawierające jedną literę?
whuber
@whuber hmmm dobry punkt. Być może odpowiadam na złe pytanie!
2

Podejście Monte Carlo

Szybkim i brudnym podejściem jest przeprowadzenie badania Monte Carlo. Narysuj płytek razy i dla każdego losowania płytek sprawdź, czy możesz utworzyć słowo. Oznacz, ile razy możesz utworzyć słowo przez . Pożądane prawdopodobieństwo wynosi:m k m wkmkmw

1mwm

Bezpośrednie podejście

Niech liczba słów w słowniku być podane przez . Niech będzie liczbą sposobów, w jakie możemy utworzyć słowo . Niech liczba liter potrzebnych przez słowo będzie oznaczona przez (tzn. Słowo potrzebuje liczby liter „a” itp). Oznaczają liczbę słów możemy tworzyć z wszystkich płytek przez .t y s p e ty m , m b , . . . , m z s th m a NStssthsthma,mb,...,mzsthmaN

N=(nk)

i

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

(Uwzględnienie wpływu żetonów symboli wieloznacznych jest nieco trudniejsze. Na razie odłożę ten problem.)

Zatem pożądane prawdopodobieństwo wynosi:

1stsN

źródło
Szybkie i brudne podejście może nie być takie szybkie! Słownik może zawierać 100 000 słów, a poszukiwanie dopasowania danych kafelków może być katastrofą kodującą.
shabbychef
@shabbychef Jest to coś dobrze zrobionego, aby pasowało do sprawdzania pisowni. Patrz na przykład n3labs.com/pdf/lexicon-squeeze.pdf
@shabbychef Reg monte-carlo- jeśli słownik jest posortowany, dopasowanie powinno być dość szybkie nie? W każdym razie bezpośrednie podejście, które nakreśliłem wcześniej, było wadliwe. Naprawiłem to. Problem w moim wcześniejszym rozwiązaniu polegał na tym, że to samo słowo można utworzyć na wiele sposobów (np. „Nietoperz”, „b * t” itp.).
1
@shabbychef Po dalszej refleksji zgadzam się z Tobą, że podejście Monte Carlo nie zadziała. Jedną kwestią jest to, że musisz dowiedzieć się, jakie słowa możesz utworzyć za pomocą k płytek, a drugą jest to, że możesz utworzyć wiele słów za pomocą k płytek. Obliczanie tych kombinacji z k płytek prawdopodobnie nie jest takie łatwe.
1
@Srikant Thanks. Wydaje się, że twoja formuła zakłada, że ​​musisz użyć wszystkich liter k, aby utworzyć słowo, ale nie sądzę, że o to prosi OP. (W każdym razie nie tak gra się w Scrabble.) Przy takim domniemanym założeniu jesteś na dobrej drodze, ale musisz zmodyfikować algorytm: nie wolno powtarzać obliczeń dla słów w słowniku, które są wzajemnymi permutacjami. Na przykład nie możesz odejmować zarówno t_ {stop}, jak i t_ {post} w formule. (Jest to łatwa modyfikacja do wdrożenia.)
whuber