Wymagana jest formuła . Niestety sytuacja jest tak skomplikowana, że wydaje się, że każda formuła będzie jedynie okrężnym sposobem wyliczenia wszystkich możliwości. Zamiast tego ta odpowiedź oferuje algorytm, który jest (a) równoznaczny ze wzorem obejmującym sumy iloczynów współczynników dwumianowych i (b) może być przeniesiony na wiele platform.
Aby uzyskać taką formułę, podziel możliwości na wzajemnie rozłączne grupy na dwa sposoby: w zależności od liczby liter spoza słowa wybranych w stojaku (niech to będzie ) i według liczby symboli wieloznacznych (pustych) niech to będzie wagowo ). Gdy w stojaku znajduje się r = 7 płytek, N dostępnych płytek, M dostępnych płytek z literami niewymienionymi w słowie, a W = 2 puste pola, liczba możliwych wyborów podana przez ( m , w ) wynosimwr=7NMW=2(m,w)
( Mm) ( Ww) ( N- M- W.r- m - w)
ponieważ wybory liter niebędących słowami, spacji i liter są niezależne od( m , w , r ) .
Zmniejsza to problem ze znalezieniem liczby sposobów przeliterowania słowa przy wybieraniu tylko z kafelków reprezentujących litery słowa, biorąc pod uwagę, że są dostępne puste pola i zostaną płytki . Sytuacja jest chaotyczna i wydaje się, że nie ma zamkniętej formuły. Na przykład, jeśli pustych pól i niesymetryczne litery zostaną narysowane, pozostaną dokładnie cztery litery, które przeliterują „boot”, które zostały narysowane z kafelków „b”, „o” i „t” . Biorąc pod uwagę, że są „b”, „o” ir - m - w w = 0 m = 3 2 8 6wr - m - ww = 0m = 32)86„t” w zestawie kafelków Scrabble, istnieją pozytywne prawdopodobieństwa rysowania (multisetów) „bboo”, „bbot”, „bbtt”, „booo”, „boot”, „bott”, „bttt”, „oooo ”,„ ooot ”,„ oott ”,„ ottt ”i„ tttt ”, ale tylko jedno z tych zaklęć„ boot ”. I to był łatwy przypadek! Na przykład, zakładając, że stojak zawiera pięć losowo wybranych kafelków z płytek „o”, „b” i „t”, wraz z oboma pustymi polami, istnieje wiele innych sposobów na przeliterowanie „rozruchu” - i nie przeliterowanie go. Na przykład „boot” można przeliterować z „__boott” i „__bbttt”, ale nie z „__ttttt”.
Liczenie to - sedno problemu - można rozwiązać rekurencyjnie. Opiszę to na przykładzie. Załóżmy, że chcemy policzyć pisownię „boot” z jednym pustym i czterema dodatkowymi kafelkami z kolekcji płytek „b”, „o” i „t” (skąd pozostałe dwa kafelki pokazują niepuste litery nie w { „b”, „o”, „t”}). Rozważ pierwszą literę „b”:
„B” można narysować na z dwóch dostępnych kafelków „b”. Zmniejsza to problem do zliczania liczby sposobów przeliterowania przyrostka „oot” przy użyciu obu pustych pól i tylko trzech kolejnych płytek z kolekcji płytek „o” i „t”.( 21)
Jeden pusty może być oznaczony jako „b”. Zmniejsza to problem do zliczania liczby sposobów pisowni „oot” przy użyciu pozostałego pustego miejsca i tylko trzech kolejnych kafelków z kolekcji płytek „o” i „t”.
Zasadniczo kroki (1) i (2) - które są rozłączne, a zatem przyczyniają się dodatkowo do obliczeń prawdopodobieństwa - mogą zostać zaimplementowane jako pętla nad możliwą liczbą odstępów, które mogą być użyte dla pierwszej litery. Ograniczony problem rozwiązano rekurencyjnie. Podstawowy przypadek występuje, gdy pozostała jedna litera, dostępna jest pewna liczba płytek z tą literą, a także mogą być pewne puste miejsca w stojaku. Musimy tylko upewnić się, że liczba pustych miejsc w stojaku plus liczba dostępnych płytek wystarczą, aby uzyskać pożądaną ilość tej ostatniej litery.
Oto Rkod kroku rekurencyjnego. rackzwykle wynosi , jest tablicą zliczeń liter (np. ), jest podobną strukturą podającą liczbę dostępnych płytek z tymi literami i jest liczbą założonych pustych miejsc w szafie.7wordc(b=1, o=2, t=1)alphabetwild
f <- function(rack, word, alphabet, wild) {
if (length(word) == 1) {
return(ifelse(word > rack+wild, 0, choose(alphabet, rack)))
}
n <- word[1]
if (n <= 0) return(0)
m <- alphabet[1]
x <- sapply(max(0, n-wild):min(m, rack),
function(i) {
choose(m, i) * f(rack-i, word[-1], alphabet[-1], wild-max(0, n-i))
})
return(sum(x))
}
Interfejs tej funkcji określa standardowe kafelki Scrabble, konwertuje dane słowo na wielosetową strukturę danych i wykonuje podwójną sumę na i w . Oto gdzie współczynniki dwumianowe ( Mmw i ( W( Mm) są obliczane i mnożone.(Ww)
scrabble <- function(sword, n.wild=2, rack=7,
alphabet=c(a=9,b=2,c=2,d=4,e=12,f=2,g=3,h=2,i=9,j=1,k=1,l=4,m=2,
n=6,o=8,p=2,q=1,r=6,s=4,t=6,u=4,v=2,w=2,x=1,y=2,z=1),
N=sum(alphabet)+n.wild) {
word = sort(table(strsplit(sword, NULL))) # Sorting speeds things a little
a <- sapply(names(word), function(s) alphabet[s])
names(a) <- names(word)
x <- sapply(0:n.wild, function(w) {
sapply(sum(word):rack-w,
function(i) {
f(i, word, a, wild=w) *
choose(n.wild, w) * choose(N-n.wild-sum(a), rack-w-i)
})
})
return(list(numerator = sum(x), denominator = choose(N, rack),
value=sum(x) / choose(N, rack)))
}
Wypróbujmy to rozwiązanie i zmierzmy je do końca. Poniższy test wykorzystuje te same dane wejściowe wykorzystane w symulacjach @Rasmus Bååth :
system.time(x <- sapply(c("boot", "red", "axe", "zoology"), scrabble))
To urządzenie podaje całkowity czas, który upłynął sekundy: dość szybko. Wyniki?0.05
> x
boot red axe zoology
numerator 114327888 1249373480 823897928 11840
denominator 16007560800 16007560800 16007560800 16007560800
value 0.007142118 0.07804896 0.0514693 7.396505e-07
Prawdopodobieństwo dla „bagażnik” z dokładnie równa wartości 2381831 / +333.490.850 uzyskanego w innym moją odpowiedź (który używa podobnej metody, ale kanapy go w mocniejszy ramach wymagającego symboliczną platformę algebra obliczeniowej). Prawdopodobieństwa dla wszystkich czterech słów są dość blisko do symulacji Baas (który nie mógł się spodziewać, aby dać dokładną wartość „zoologia” ze względu na jego niskie prawdopodobieństwo 11840 / 16007560800 , który jest mniej niż jedna na milion).114327888/160075608002381831/33349085011840/16007560800,