Esta es una (!) comentarios sobre el buen trabajo de @vqv ha publicado en este hilo. Se persigue el objetivo de obtener una respuesta definitiva. Él ha hecho el trabajo duro de simplificar el diccionario. Todo lo que queda es para explotarlo al máximo. Sus resultados sugieren que un ataque de fuerza bruta solución es factible. Después de todo, incluyendo un comodín que existen en la mayoría de los $27^7 = 10,460,353,203$ palabras que uno puede hacer con 7 caracteres, y parece que en menos de 1/10000 de ellos-por ejemplo, alrededor de un millón--no incluyen algunos de word válido.
El primer paso es aumentar el mínimo diccionario con un carácter comodín "?". 22 de las cartas que aparecen en palabras de dos letras (c, q, v, z). Lindan con un comodín a los 22 letras y agregar al diccionario: {?, b?, d?, ..., y?} ahora están en. Del mismo modo podemos inspeccionar el mínimo de palabras de tres letras, causando algunas palabras adicionales a aparecer en el diccionario. Por último, añadimos "??" para el diccionario. Después de la eliminación de repeticiones que el resultado, que contiene 342 mínimo de palabras.
Una elegante manera de proceder, que utiliza una cantidad muy pequeña de codificación de hecho, es ver este problema como una expresión algebraica uno. Una palabra, considerado como un desordenado conjunto de letras, es sólo un monomio. Por ejemplo, "polainas" es el monomio $a p s^2 t$. El diccionario, por tanto, es una colección de monomials. Parece
$$\{a^2 a, b, d, ..., o z \psi, w x \psi \psi^2\}$$
(donde, para evitar confusiones, he escrito $\psi$ para el carácter comodín).
Un rack contiene una palabra válida si y sólo si esa palabra se divide el rack.
Una más abstracto, pero muy poderoso, la manera de decir esto es que el diccionario se genera un ideal $I$ en el polinomio anillo de $R = \mathbb{Z}[a, b, \ldots, z, \psi]$ y que los bastidores con palabras válidas convierte en cero en el cociente del anillo $R/I$, mientras que los bastidores sin palabras válidas siendo distinto de cero en el cociente. Si se forma la suma de todos los bastidores en $R$ y se calcula en este cociente del anillo, entonces el número de bastidores sin palabras es igual al número de los distintos monomials en el cociente.
Además, la suma de todos los bastidores en $R$ es fácil de expresar. Deje que $\alpha = a + b + \cdots + z + \psi$ ser la suma de todas las letras del alfabeto. $\alpha^7$ contiene un monomio por cada rack. (Como un bono adicional, sus coeficientes de contar el número de maneras en las que cada estante puede ser formado, lo que nos permite calcular la probabilidad de que si nos gusta.)
Como un simple ejemplo (para ver cómo funciona esto), supongamos que (a) no usar caracteres comodín y (b) todas las letras de la "a" a la "x" se consideran palabras. Entonces la única posible bastidores de que las palabras no pueden ser formados debe consistir enteramente de y y z. Calculamos $\alpha=(a+b+c+\cdots+x+y+z)^7$ modulo el ideal generado por $\{a,b,c, \ldots, x\}$ un paso a la vez, por lo tanto:
$$\eqalign{
\alpha^0 y= 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{.}
}$$
Podemos leer en la posibilidad de obtener un no-palabra bastidor de la respuesta final, $y^7 + 7 y^6 z + 21 y^5 z^2 + 35 y^4 z^3 + 35 s^3 z^4 + 21 y^2 z^5 +
7 y z^6 + z^7$: cada coeficiente cuenta las formas en que la correspondiente bastidor puede ser dibujado. Por ejemplo, hay 21 (de 26^7 posibles) formas para dibujar 2 y y 5 z debido a que el coeficiente de $y^2 z^5$ es igual a 21.
Desde la primaria los cálculos, es obvio que esta es la respuesta correcta. El punto es que este procedimiento funciona independientemente de los contenidos del diccionario.
Observe cómo la reducción de la potencia del modulo el ideal que en cada etapa se reduce el cálculo: es el acceso directo revelada por este enfoque. (Final del ejemplo.)
Polinomio de álgebra sistemas de aplicación de estos cálculos. Por ejemplo, aquí se Mathematica código:
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]
(El diccionario puede ser construido en una forma sencilla de @vqv min.dict; me ponga una línea aquí mostrando que es lo suficientemente corto como para ser especificado directamente si así lo desea).
El resultado-que lleva a los diez minutos de computación--es 577958. (NB En una versión anterior de este mensaje, yo había hecho un pequeño error en la preparación del diccionario y obtuvo 577940. He modificado el texto para reflejar lo que espero que ahora son los resultados correctos!) Un poco menos que los millones o así me lo esperaba, pero del mismo orden de magnitud.
Para calcular la probabilidad de obtener un rack, tenemos que tener en cuenta el número de maneras en las que el bastidor puede ser dibujado. Como vimos en el ejemplo, esto es igual a su coeficiente en $\alpha^7$. La probabilidad de extraer algunas tales rack es la suma de todos estos coeficientes, se encuentran fácilmente por la configuración de todas las cartas igual a 1:
nonwords /. (# -> 1) & /@ (List @@ alphabet)
La respuesta es igual a 1066056120, dando una oportunidad de 10.1914% de dibujo de un bastidor de que no hay una palabra puede ser formado (si todas las letras son igualmente probables).
Cuando las probabilidades de las letras varían, basta con sustituir cada letra con su posibilidad de ser dibujada:
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)
La salida es 1.079877553303%, la exacta respuesta (aunque usando un modelo aproximado, dibujo con reemplazo). Mirando hacia atrás, tomó cuatro líneas para introducir los datos (alfabeto, diccionario, y el alfabeto de frecuencias) y sólo tres líneas para hacer el trabajo: describir cómo tomar la siguiente potencia de $\alpha$ modulo I$$, tomar la 7ª potencia de forma recursiva, y sustituir las probabilidades para las letras.
