Kemungkinan tidak menggambar sepatah kata pun dari kantong surat di Scrabble

Misalkan Anda memiliki tas dengan ubin, masing-masing dengan huruf di atasnya. Ada ubin dengan huruf 'A', dengan 'B', dan seterusnya, dan 'wildcard' (kami memiliki ). Misalkan Anda memiliki kamus dengan jumlah kata yang terbatas. Anda memilih ubin dari kantong tanpa pengganti. Bagaimana Anda menghitung (atau memperkirakan) probabilitas bahwa Anda dapat membentuk nol kata dari kamus mengingat ubin dipilih?n A n B n ∗ n = n A + n B + … + n Z + n ∗ k $n$$n_A$$n_B$$n_*$$n = n_A + n_B + \ldots + n_Z + n_*$$k$$k$

Bagi mereka yang tidak terbiasa dengan Scrabble (TM), karakter wildcard dapat digunakan untuk mencocokkan huruf apa pun. Dengan demikian kata [ BOOT ] dapat 'dieja' dengan ubin 'B', '*', 'O', 'T'.

Untuk memberikan gambaran tentang skala masalah, bertubuh kecil, seperti 7, sekitar 100, dan kamus berisi sekitar 100.000 kata ukuran atau lebih kecil.n $k$$n$$k$

sunting: Dengan 'membentuk kata', maksud saya kata dengan panjang tidak lebih dari . Jadi, jika kata [ A ] ada di kamus, maka dengan menggambar bahkan satu 'A' dari tas, seseorang telah 'membentuk kata'. Masalah wildcard secara radikal disederhanakan jika seseorang dapat berasumsi ada kata-kata dengan panjang 1 dalam kamus. Karena jika ada, setiap undian wildcard secara otomatis dapat mencocokkan panjang 1 kata, dan dengan demikian seseorang dapat berkonsentrasi pada kasus di mana tidak ada wildcard. Jadi, bentuk masalah yang lebih licin tidak memiliki kata 1 huruf dalam kamus.$k$

Juga, saya harus secara eksplisit menyatakan bahwa urutan surat-surat yang diambil dari tas tidak material. Orang tidak harus menggambar huruf dalam urutan kata yang 'benar'.

Ini adalah komentar (panjang!) Pada karya bagus yang telah diposting @vqv di utas ini. Ini bertujuan untuk mendapatkan jawaban yang pasti. Dia telah melakukan kerja keras menyederhanakan kamus. Yang tersisa hanyalah mengeksploitasinya secara maksimal. Hasilnya menunjukkan bahwa solusi brute-force layak dilakukan . Lagipula, termasuk wildcard, paling banyak ada kata yang dapat dibuat dengan 7 karakter, dan sepertinya kurang dari 1/10000 di antaranya - katakanlah, sekitar satu juta - akan gagal memasukkan beberapa kata yang valid. $27^7 = 10,460,353,203$

Langkah pertama adalah menambah kamus minimal dengan karakter wildcard, "?". 22 huruf muncul dalam kata-kata dua huruf (semua kecuali c, q, v, z). Sesuaikan wildcard ke 22 huruf tersebut dan tambahkan ke kamus: {a ?, b?, D ?, ..., y?} Sekarang sudah masuk. Demikian pula kita dapat memeriksa kata-kata tiga huruf minimal, menyebabkan beberapa kata tambahan muncul di kamus. Akhirnya, kami menambahkan "??" ke kamus. Setelah menghapus pengulangan yang menghasilkan, itu berisi 342 kata-kata minimal.

Cara yang elegan untuk melanjutkan - yang menggunakan jumlah pengkodean yang sangat kecil - adalah untuk melihat masalah ini sebagai aljabar . Sebuah kata, yang dianggap sebagai seperangkat huruf yang tidak teratur, hanyalah sebuah monomial. Misalnya, "pertengkaran" adalah monomial . Kamus karena itu adalah kumpulan monomial. Sepertinya$a p s^2 t$

$$\{a^2, a b, a d, ..., o z \psi, w x \psi, \psi^2\}$$

(di mana, untuk menghindari kebingungan, saya telah menulis untuk karakter wildcard).$\psi$

Rak berisi kata yang valid jika dan hanya jika kata itu membagi rak.

Cara yang lebih abstrak, tetapi sangat kuat, untuk mengatakan ini adalah bahwa kamus menghasilkan ideal dalam cincin polinomial R = Z [ a , b , … , z , ψ ] dan bahwa rak dengan kata-kata yang valid menjadi nol dalam hasil bagi dering R / I , sedangkan rak tanpa kata-kata yang valid tetap tidak nol dalam hasil bagi. Jika kita membentuk jumlah semua rak dalam R dan menghitungnya dalam cincin hasil bagi ini, maka jumlah rak tanpa kata sama dengan jumlah monomial yang berbeda dalam hasil bagi.$I$$R = \mathbb{Z}[a, b, \ldots, z, \psi]$$R/I$$R$

Selain itu, jumlah semua rak di mudah untuk diekspresikan. Biarkan α = a + b + ⋯ + z + ψ menjadi jumlah dari semua huruf dalam alfabet. α 7 berisi satu monomial untuk setiap rak. (Sebagai bonus tambahan, koefisiennya menghitung jumlah cara setiap rak dapat dibentuk, memungkinkan kita menghitung probabilitasnya jika kita mau.)$R$$\alpha = a + b + \cdots + z + \psi$$\alpha^7$

Sebagai contoh sederhana (untuk melihat bagaimana ini bekerja), misalkan (a) kita tidak menggunakan wildcard dan (b) semua huruf dari "a" hingga "x" dianggap sebagai kata. Maka satu-satunya rak yang memungkinkan dari mana kata-kata tidak dapat dibentuk harus seluruhnya terdiri dari y dan z. Kami menghitung modulo yang ideal dihasilkan oleh { a , b , c , … , x } satu langkah pada satu waktu, dengan demikian:$\alpha=(a+b+c+\cdots+x+y+z)^7$$\{a,b,c, \ldots, x\}$

$$\eqalign{ \alpha^0 &= 1 \cr \alpha^1 &= a+b+c+\cdots+x+y+z \equiv y+z \mod I \cr \alpha^2 &\equiv (y+z)(a+b+\cdots+y+z) \equiv (y+z)^2 \mod I \cr \cdots &\cr \alpha^7 &\equiv (y+z)^6(a+b+\cdots+y+z) \equiv (y+z)^7 \mod I \text{.} }$$

Kita dapat membaca peluang mendapatkan rak non-kata dari jawaban akhir, : masing-masing koefisien menghitung cara rak yang sesuai dapat ditarik. Misalnya, ada 21 (dari 26 ^ 7 kemungkinan) cara untuk menggambar 2 y dan 5 z karena koefisien $y^7 + 7 y^6 z + 21 y^5 z^2 + 35 y^4 z^3 + 35 y^3 z^4 + 21 y^2 z^5 + 7 y z^6 + z^7$ sama dengan 21.$y^2 z^5$

Dari perhitungan dasar, jelas ini adalah jawaban yang benar. Intinya adalah bahwa prosedur ini berfungsi terlepas dari isi kamus.

Perhatikan bagaimana mengurangi daya modulo ideal pada setiap tahap mengurangi perhitungan: itulah cara pintas yang diungkapkan oleh pendekatan ini. (Akhir contoh.)

Sistem aljabar polinomial menerapkan perhitungan ini . Misalnya, ini adalah kode 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]

(Kamus dapat dibangun secara langsung dari min.dict @ vqv; Saya meletakkan garis di sini yang menunjukkan bahwa itu cukup pendek untuk ditentukan secara langsung jika Anda suka.)

Output - yang memerlukan sepuluh menit perhitungan - adalah 577958. ( NB Dalam versi sebelumnya dari pesan ini saya telah membuat kesalahan kecil dalam mempersiapkan kamus dan memperoleh 577940. Saya telah mengedit teks untuk mencerminkan apa yang saya harap sekarang adalah hasil yang benar!) Sedikit kurang dari satu juta atau lebih yang saya harapkan, tetapi dengan urutan yang sama besarnya.

Untuk menghitung kemungkinan mendapatkan rak seperti itu, kita perlu memperhitungkan sejumlah cara di mana rak dapat ditarik. Seperti yang kita lihat dalam contoh, ini sama dengan koefisiennya di . Peluang menggambar beberapa rak tersebut adalah jumlah dari semua koefisien ini, mudah ditemukan dengan menyetel semua huruf sama dengan 1:$\alpha^7$

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

Jawabannya sama dengan 1066056120, memberikan peluang 10,1914% menggambar rak dari mana tidak ada kata yang valid dapat dibentuk (jika semua huruf sama-sama kemungkinan).

Ketika probabilitas surat berbeda-beda, ganti saja setiap huruf dengan kemungkinan ditarik:

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)

Outputnya adalah 1,079877553303%, jawaban yang tepat (meskipun menggunakan model perkiraan, menggambar dengan penggantian). Melihat kembali, butuh empat baris untuk memasukkan data (alfabet, kamus, dan alfabet frekuensi) dan hanya tiga baris untuk melakukan pekerjaan: menjelaskan bagaimana untuk mengambil kekuatan berikutnya modulo saya , mengambil kekuasaan 7 rekursif, dan mengganti probabilitas untuk surat-surat itu.$\alpha$$I$

Sangat sulit untuk menggambar rak yang tidak mengandung kata yang valid di Scrabble dan variannya. Di bawah ini adalah program R yang saya tulis untuk memperkirakan probabilitas bahwa rak 7-ubin awal tidak mengandung kata yang valid. Ini menggunakan pendekatan monte carlo dan leksikon Words With Friends (saya tidak dapat menemukan leksikon Scrabble resmi dalam format yang mudah). Setiap percobaan terdiri dari menggambar rak 7-ubin, dan kemudian memeriksa apakah rak berisi kata yang valid.

Kata-kata minimal

Anda tidak perlu memindai seluruh leksikon untuk memeriksa apakah rak berisi kata yang valid. Anda hanya perlu memindai leksikon minimal yang terdiri dari kata-kata minimal . Sebuah kata minimal jika tidak mengandung kata lain sebagai himpunan bagian. Misalnya 'em' adalah kata minimal; 'kosong' tidak. Intinya adalah bahwa jika sebuah rak berisi kata x maka itu juga harus mengandung subset dari x . Dengan kata lain: rak tidak mengandung kata-kata jika tidak mengandung kata-kata minimal. Untungnya, sebagian besar kata dalam leksikon tidak minimal, sehingga dapat dihilangkan. Anda juga dapat menggabungkan kata-kata yang setara permutasi. Saya dapat mengurangi leksikon Words With Friends dari 172.820 menjadi 201 kata minimal.

Wildcard dapat dengan mudah ditangani dengan memperlakukan rak dan kata-kata sebagai distribusi atas surat-surat. Kami memeriksa apakah rak berisi kata dengan mengurangi satu distribusi dari yang lain. Ini memberi kita jumlah setiap huruf yang hilang dari rak. Jika jumlah angka itu jumlah wildcard, maka kata itu ada di rak.$\leq$

Satu-satunya masalah dengan pendekatan monte carlo adalah bahwa peristiwa yang kami minati sangat jarang terjadi. Jadi perlu banyak, banyak percobaan untuk mendapatkan perkiraan dengan kesalahan standar yang cukup kecil. Saya menjalankan program saya (disisipkan di bagian bawah) dengan percobaan dan mendapat probabilitas diperkirakan 0,004 bahwa rak awal tidak mengandung kata yang valid . Kesalahan standar estimasi estimasi itu adalah 0,0002. Hanya perlu beberapa menit untuk berjalan di Mac Pro saya, termasuk mengunduh leksikon.$N=100,000$

Saya akan tertarik melihat apakah seseorang dapat datang dengan algoritma tepat yang efisien. Pendekatan naif berdasarkan inklusi-eksklusi tampaknya bisa melibatkan ledakan kombinatorial.

Inklusi-pengecualian

Saya pikir ini adalah solusi yang buruk, tapi ini sketsa yang tidak lengkap. Pada prinsipnya Anda dapat menulis program untuk melakukan perhitungan, tetapi spesifikasinya akan berliku.

Probabilitas yang ingin kita hitung adalah Peristiwa di dalam probabilitas di sisi kanan adalah gabungan peristiwa: P ( k -tile rak mengandung kata ) = P ( ∪ x ∈ M { k -tile rak berisi  x } ) , di mana

$$P(k\text{-tile rack does not contain a word}) = 1 - P(k\text{-tile rack contains a word}) .$$ $$P(k\text{-tile rack contains a word}) = P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right),$$ $M$adalah leksikon minimal. Kami dapat mengembangkannya menggunakan rumus inklusi-pengecualian. Ini melibatkan mempertimbangkan semua persimpangan yang mungkin dari peristiwa di atas. Mari menunjukkan kekuatan set M , yaitu himpunan semua himpunan bagian yang mungkin dari M . Kemudian $\mathcal{P}(M)$$M$$M$ $$\begin{align} &P(k\text{-tile rack contains a word}) \\ &= P\left(\cup_{x \in M} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{j=1}^{|M|} (-1)^{j-1} \sum_{S \in \mathcal{P}(M) : |S| = j} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \end{align}$$

$$\cap_{x \in S} \{ k\text{-tile rack contains }x \}$$ $S$

Kemudian

$$\begin{align} &P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} \right) \\ &= \sum_{w=0}^{n_{*}} P\left( \cap_{x \in S} \{ k\text{-tile rack contains }x \} | k\text{-tile rack contains } w \text{ wildcards} \right) \\ &\quad \times P(k\text{-tile rack contains } w \text{ wildcards}) . \end{align}$$

$2^{|M|}$$2^{|M|} \approx 3.2 \times 10^{60}$

Memindai semua kemungkinan rak

$k$rak -tile sampai kita mendapatkan set rak yang tidak mengandung kata-kata. Untuk Scrabble (atau Words With Friends) jumlah rak 7-ubin yang mungkin ada dalam puluhan miliar. Menghitung jumlah orang yang tidak mengandung kata yang mungkin harus dilakukan dengan beberapa lusin baris kode R. Tapi saya pikir Anda harus bisa melakukan lebih baik daripada hanya menghitung semua rak yang mungkin. Misalnya, 'aa' adalah kata minimal. Itu segera menghilangkan semua rak yang berisi lebih dari satu 'a'. Anda bisa mengulanginya dengan kata lain. Memori seharusnya tidak menjadi masalah bagi komputer modern. Rak Scrabble 7-ubin membutuhkan kurang dari 7 byte penyimpanan. Paling buruk kami akan menggunakan beberapa gigabyte untuk menyimpan semua rak yang mungkin, tapi saya pikir itu juga bukan ide yang baik. Seseorang mungkin ingin lebih memikirkan hal ini.

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)), ")")

Srikant benar: belajar di Monte Carlo adalah jalan yang harus ditempuh. Ada dua alasan. Pertama, jawabannya sangat tergantung pada struktur kamus. Dua ekstrem adalah (1) kamus berisi setiap kata dengan satu huruf. Dalam hal ini, peluang untuk tidak membuat kata dalam undian$1$atau lebih banyak huruf adalah nol. (2) Kamus hanya berisi kata-kata yang dibentuk dari satu huruf ( misalnya , "a", "aa", "aaa", dll .). Kesempatan untuk tidak membuat kata dalam undian$k$huruf mudah ditentukan dan jelas bukan nol. Setiap jawaban pasti bentuk tertutup harus menggabungkan seluruh struktur kamus dan akan menjadi formula yang benar-benar mengerikan dan panjang.

Alasan kedua adalah bahwa MC memang layak: Anda hanya harus melakukannya dengan benar. Paragraf sebelumnya memberikan petunjuk: jangan hanya menghasilkan kata-kata secara acak dan mencarinya; sebagai gantinya, menganalisis kamus terlebih dahulu dan memanfaatkan strukturnya.

Salah satu cara mewakili kata-kata dalam kamus sebagai pohon. Pohon itu berakar pada simbol dan ranting kosong pada setiap huruf sampai ke bawah; daunnya (tentu saja) adalah kata-kata itu sendiri. Namun, kami juga dapat memasukkan semua permutasi nontrivial dari setiap kata ke pohon, juga (hingga$k!-1$dari mereka untuk setiap kata). Ini dapat dilakukan secara efisien karena seseorang tidak harus menyimpan semua permutasi tersebut; hanya ujung-ujung pohon perlu ditambahkan. Daunnya tetap sama. Bahkan, ini dapat disederhanakan lebih lanjut dengan menegaskan bahwa pohon tersebut harus diikuti dalam urutan abjad .

Dengan kata lain, untuk menentukan apakah multiset dari $k$karakter ada di kamus, pertama mengatur elemen ke dalam urutan, lalu cari "kata" yang diurutkan ini di pohon yang dibangun dari perwakilan kata yang diurutkan di kamus asli. Ini sebenarnya akan lebih kecil dari pohon asli karena menggabungkan semua set kata yang setara, seperti {stop, post, pot, opts, spot}. Bahkan, dalam kamus bahasa Inggris, kelas kata ini tidak akan pernah tercapai karena "begitu" akan ditemukan terlebih dahulu. Mari kita lihat ini dalam aksi. Multiset yang diurutkan adalah "opst"; "o" akan bercabang ke semua kata yang hanya berisi huruf {o, p, ..., z}, "p" akan bercabang ke semua kata yang hanya berisi {o, p, ..., z} dan paling banyak satu "o", dan akhirnya "s" akan bercabang ke daun "begitu"!

Diperlukan modifikasi untuk menangani wildcard: Saya akan membiarkan tipe programmer di antara Anda memikirkannya. Itu tidak akan menambah ukuran kamus (sebenarnya akan menguranginya); itu akan sedikit memperlambat traversal pohon, tetapi tanpa mengubahnya dengan cara mendasar. Dalam kamus apa pun yang berisi kata satu huruf, seperti bahasa Inggris ("a", "i"), tidak ada kerumitan: kehadiran wildcard berarti Anda dapat membentuk sebuah kata! (Ini mengisyaratkan bahwa pertanyaan awal mungkin tidak semenarik kedengarannya.)

Hasilnya adalah bahwa pencarian kamus tunggal membutuhkan (a) pengurutan a $k$multiset-newsletter dan (b) melintasi tidak lebih dari $k$ujung-ujung pohon. Waktu berjalan adalah$O(k \log(k))$. If you cleverly generate random multisets in sorted order (I can think of several efficient ways to do this), the running time reduces to $O(k)$. Multiply this by the number of iterations to get the total running time.

I bet you could conduct this study with a real Scrabble set and a million iterations in a matter of seconds.

Pendekatan Monte Carlo

Pendekatan cepat dan kotor adalah melakukan studi monte carlo. Seri$k$ ubin $m$ waktu dan untuk setiap undian $k$ tiles see if you can form a word. Denote the number of times you could form a word by $m_w$. The desired probability would be:

$$1 - \frac{m_w}{m}$$

Direct Approach

Let the number of words in the dictionary be given by $S$. Let $t_s$ be the number of ways in which we can form the $s^\mbox{th}$ word. Let the number of letters needed by the $s^\mbox{th}$ word be denoted by ${m_a, m_b, ..., m_z}$ (i.e., the $s^\mbox{th}$ word needs $m_a$ number of 'a' letters etc). Denote the number of words we can form with all tiles by $N$.

$$N = \binom{n}{k}$$

and

$$t_s = \binom{n_a}{m_a} \binom{n_b}{m_b} ... \binom{n_z}{m_z}$$

(Including the impact of wildcard tiles is a bit trickier. I will defer that issue for now.)

Thus, the desired probability is:

$$1 - \frac{\sum_s{t_s}}{N}$$