Предположим, у вас была сумка с плитками, на каждой из которых была буква. Есть тайлы с буквой 'A', с 'B' и т. Д., И плитки с «подстановочными знаками» (у нас есть ). Предположим, у вас был словарь с конечным числом слов. Вы выбираете плиток из сумки без замены. Как бы вы вычислили (или оценили) вероятность того, что вы сможете сформировать ноль слов из словаря с учетом выбранных плиток?
Для тех, кто не знаком с Scrabble (TM), подстановочный знак может использоваться, чтобы соответствовать любой букве. Таким образом, слово [ BOOT ] может быть «написано» с плитками «B», «*», «O», «T».
Чтобы дать некоторое представление о масштабе проблемы, является небольшим, например 7, составляет около 100, а словарь содержит около 100 000 слов размером или меньше.
редактировать: под словом «сформировать слово» я подразумеваю слово длиной не более . Таким образом, если слово [ A ] находится в словаре, то, вытянув хотя бы одну букву «A» из сумки, можно «сформировать слово». Проблема подстановочных знаков радикально упрощается, если предположить, что в словаре есть слова длиной 1. Ибо, если есть, любой подстановочный знак автоматически может соответствовать слову длины 1, и, таким образом, можно сконцентрироваться на случае, когда нет подстановочных знаков. Таким образом, в более скользкой форме задачи нет слов из 1 буквы в словаре.
Также я должен прямо заявить, что порядок, в котором буквы извлекаются из сумки, не имеет значения. Не нужно рисовать буквы в «правильном» порядке слова.
источник
Ответы:
Это (длинный!) Комментарий к хорошей работе, которую @vqv опубликовал в этой теме. Он направлен на получение окончательного ответа. Он проделал тяжелую работу по упрощению словаря. Все, что остается, - это использовать его в полной мере. Его результаты предполагают, что решение грубой силы возможно . В конце концов, включая подстановочный знак, существует не более слов, которые можно произнести с помощью 7 символов, и похоже, что менее 1/10000 из них, скажем, около миллиона, не в состоянии включить какое-либо действительное слово.277=10,460,353,203
Первым шагом является добавление минимального словаря подстановочным знаком «?». 22 буквы появляются в двухбуквенных словах (все, кроме c, q, v, z). Присоедините подстановочный знак к этим 22 буквам и добавьте их в словарь: {a ?, b ?, d ?, ..., y?} Теперь в. Аналогично мы можем проверить минимальные трехбуквенные слова, вызывая некоторые дополнительные слова появляться в словаре. Наконец, мы добавляем "??" в словарь. После удаления повторений, которые в результате, он содержит 342 минимальных слова.
Элегантный способ продолжить - тот, который действительно использует очень небольшое количество кодирования - это рассматривать эту проблему как алгебраическую . Слово, рассматриваемое как неупорядоченный набор букв, является просто мономом. Например, "spats" - это моном . Таким образом, словарь представляет собой набор мономов. Это выглядит какaps2t
(где, чтобы избежать путаницы, я написал для символа подстановки).ψ
Стойка содержит правильное слово, если и только если это слово разделяет стойку.
Более абстрактный, но чрезвычайно мощный способ сказать, что словарь генерирует идеал в кольце многочленов R = Z [ a , b , … , z , ψ ] и что стойки с действительными словами становятся равными нулю в частном. ring R / I , тогда как стойки без допустимых слов остаются ненулевыми в частном. Если мы сформируем сумму всех стоек в R и вычислим ее в этом фактор-кольце, точисло стоек без слов будет равным количеству различных мономов в фактор-группе.я R = Z [ a , b , … , z, ψ ] R / I р
Кроме того, сумма всех стоек в легко выразить. Пусть α = a + b + ⋯ + z + ψ - сумма всех букв в алфавите. α 7 содержит один моном для каждой стойки. (В качестве дополнительного бонуса его коэффициенты подсчитывают количество способов, которыми может быть сформирована каждая стойка, что позволяет нам вычислять ее вероятность, если мы захотим.)р α = a + b + ⋯ + z+ ψ α7
В качестве простого примера (чтобы увидеть, как это работает), предположим, что (а) мы не используем подстановочные знаки и (б) все буквы от «а» до «х» считаются словами. Тогда единственно возможные стойки, из которых не могут быть образованы слова, должны состоять целиком из y и z. Вычисляем по модулю идеала, порожденного { a , b , c , … , x }, по одному шагу за раз, таким образом:α = ( a + b + c + ⋯ + x + y+z)7 {a,b,c,…,x}
Мы можем зачитать шанс получить не состоящую из слов стойку из окончательного ответа: : каждый коэффициент подсчитывает, каким образом можно нарисовать соответствующую стойку. Например, есть 21 (из 26 ^ 7 возможных) способов нарисовать 2 y и 5 z, потому что коэффициент yy7+7y6z+21y5z2+35y4z3+35y3z4+21y2z5+7yz6+z7 равняется 21.y2z5
Из элементарных расчетов очевидно, что это правильный ответ. Все дело в том, что эта процедура работает независимо от содержания словаря.
Обратите внимание, как уменьшение мощности по модулю идеала на каждом этапе сокращает вычисления: это сокращение, выявленное этим подходом. (Конец примера.)
Системы полиномиальной алгебры реализуют эти вычисления . Например, вот код Mathematica :
(Словарь может быть построен простым способом из min.dict @vqv; я поставил здесь строку, показывающую, что он достаточно короткий, чтобы его можно было указать напрямую, если хотите.)
Вывод - который занимает десять минут вычислений - 577958. ( NB. В более ранней версии этого сообщения я допустил небольшую ошибку при подготовке словаря и получил 577940. Я отредактировал текст, чтобы отразить то, что, я надеюсь, сейчас правильные результаты!) Чуть меньше миллиона или около того я ожидал, но того же порядка.
Чтобы рассчитать вероятность получения такой стойки, нам необходимо учесть количество способов, которыми эта стойка может быть вытянута. Как мы видели в примере, это равно его коэффициенту в . Возможность рисования некоторого такой стеллажа является суммой всех этих коэффициентов, легко найти, установив все буквы равно 1:α7
Ответ равняется 1066056120, что дает 10,19% вероятности составить стойку, из которой невозможно составить правильное слово (если все буквы одинаково вероятны).
Когда вероятности букв меняются, просто замените каждую букву ее шансом быть нарисованным:
Выход составляет 1.079877553303%, точный ответ (хотя и с использованием приблизительной модели, чертеж с заменой). Оглядываясь назад, потребовалось четыре строки для ввода данных (частоты алфавита, словаря и алфавита) и всего три строки для выполнения работы: опишите, как получить следующую степень по модулю I , взять 7-ю степень рекурсивно и подставить вероятности для букв.α I
источник
Очень сложно нарисовать стойку, в которой нет ни одного допустимого слова в Scrabble и его вариантах. Ниже приведена R-программа, которую я написал для оценки вероятности того, что начальная стойка из 7 ячеек не содержит правильного слова. Он использует подход Монте-Карло и лексикон « Слова с друзьями» (я не смог найти официальный лексикон «Эрудит» в простом формате). Каждое испытание состоит из рисования стойки из 7 плиток, а затем проверки, содержит ли стойка правильное слово.
Минимальные слова
Вам не нужно сканировать весь лексикон, чтобы проверить, содержит ли стойка правильное слово. Вам просто нужно отсканировать минимальную лексику, состоящую из минимальных слов. Слово является минимальным, если оно не содержит другого слова в качестве подмножества. Например, «em» - минимальное слово; «пусто» нет. Дело в том, что если в стойке есть слово x, то оно также должно содержать любое подмножество x . Другими словами: стойка не содержит слов, если она не содержит минимальных слов. К счастью, большинство слов в лексиконе не являются минимальными, поэтому их можно исключить. Вы также можете объединить эквивалентные слова перестановки. Мне удалось сократить словарный запас «Слова с друзьями» со 172 820 до 201 минимальных слов.
Подстановочные знаки могут быть легко обработаны, рассматривая стойки и слова как распределения по буквам. Мы проверяем, содержит ли стойка слово, вычитая одно распределение из другого. Это дает нам номер каждой буквы, отсутствующей в стойке. Если сумма этих чисел равна числу подстановочных знаков, тогда слово находится в стойке.≤
Единственная проблема с подходом Монте-Карло состоит в том, что интересующее нас событие встречается очень редко. Поэтому для получения оценки с достаточно малой стандартной ошибкой требуется много-много испытаний. Я запустил свою программу (вставил внизу) с испытаний и получилирасчетную вероятность 0,004что начальная стойка не содержит действительное слово. Расчетная стандартная ошибка этой оценки составляет 0,0002. Потребовалось всего пара минут, чтобы запустить мой Mac Pro, включая загрузку лексикона.N=100,000
Мне было бы интересно узнать, может ли кто-нибудь придумать эффективный точный алгоритм. Наивный подход, основанный на включении-исключении, кажется, что он может включать комбинаторный взрыв.
Включение-исключение
Я думаю, что это плохое решение, но в любом случае это неполный набросок. В принципе, вы можете написать программу для расчета, но спецификация будет извилистой.
Вероятность, которую мы хотим вычислить, равна Событие внутри вероятности на правой стороне представляет собой объединение событий: Р ( к -tile стойки содержит слово ) = P ( ∪ х ∈ М { K -tile стойки содержит е } ) , где
затем
Сканирование всех возможных стоек
Я думаю, что это в вычислительном отношении проще, потому что меньше возможных стоек, чем возможных подмножеств минимальных слов. Мы последовательно сокращаем множество возможныхk Стойки до тех пор, пока мы не получим набор стоек, которые не содержат слов Для Scrabble (или «Слова с друзьями») количество возможных стоек с семью тайлами составляет десятки миллиардов. Подсчет количества тех, которые не содержат возможного слова, должен быть выполним с помощью нескольких десятков строк кода R. Но я думаю, что вы должны быть в состоянии сделать лучше, чем просто перечислить все возможные стойки. Например, «аа» является минимальным словом. Это немедленно устраняет все стойки, содержащие более одного «а». Вы можете повторить с другими словами. Память не должна быть проблемой для современных компьютеров. Для стеллажа Scrabble с 7 ячейками требуется менее 7 байт. В худшем случае мы использовали бы несколько гигабайт для хранения всех возможных стоек, но я тоже не думаю, что это хорошая идея. Кто-то может захотеть больше думать об этом.
Программа Монте-Карло R
источник
Вторая причина в том, что MC действительно выполним: вы просто должны сделать это правильно. Предыдущий абзац дает подсказку: не просто генерировать слова наугад, а искать их; вместо этого сначала проанализируйте словарь и воспользуйтесь его структурой.
Для работы с подстановочными знаками необходима модификация: я позволю типам программистов из вас подумать об этом. Это не увеличит размер словаря (на самом деле это должно уменьшить его); это немного замедлит обход дерева, но не изменяет его фундаментальным образом. В любом словаре, содержащем однобуквенное слово, например в английском («a», «i»), сложностей нет: наличие подстановочного знака означает, что вы можете сформировать слово! (Это намекает на то, что оригинальный вопрос может быть не таким интересным, как кажется.)
Могу поспорить, что вы могли бы провести это исследование с реальным набором скрэббл и миллионом итераций за считанные секунды.
источник
Подход Монте-Карло
Прямой подход
а также
(Including the impact of wildcard tiles is a bit trickier. I will defer that issue for now.)
Thus, the desired probability is:
источник