¿Cómo puedo representar un pangrama de enumeración automática como una función booleana?

Question

El artículo de la wiki para pangramas autoevaluados indica que se computan utilizando diagramas de decisión binarios. He estado leyendo acerca de BDD y, desde mi entendimiento, necesitas representar algún problema como una función booleana antes de poder construir un BDD para él.

¿Cómo voy a hacer esto?

He estado pensando sobre el problema durante unos días, y estoy bastante seguro de que podría representa la entrada a la función booleana utilizando una codificación sencilla:

10000 01010 01011 10101 ... 
16A's 10B's 11C's 21D's ... 

Así que para una partida pangrama "dieciséis A, diez B, once C, veintiún D's", podría representarlo como 10000010100101110101 ...

Esto significa que hay 26 * 5 = 130 variables en la función booleana, suponiendo que restrinja el frecuencia máxima de un personaje a 32 ocurrencias.

El resultado debe ser si la representación es un pangrama de enumeración automática o no, es decir, si la oración describe su propio conjunto de frecuencias.

Para hacer esto, seguramente se requerirá una tabla hash (o varias) en el camino.

Así, por la letra E, la tabla hash podría comenzar:

one -> 1 
two -> 0 
three -> 2 
four -> 0 
five -> 1 
... 

Lo que en binario, podría ser:

1 -> 1 
10 -> 0 
11 -> 10 
100 -> 0 
101 -> 1 

Si la suma de todas las operaciones de búsqueda de la tabla E hash es igual a cinco bits de entrada correspondientes a E, entonces esa sección del pangrama de autoenumeración es correcta. Si todas las secciones son correctas, entonces la función booleana debería dar 1, de lo contrario 0.

Estoy bastante seguro de que podría averiguar cómo llevar a cabo la adición usando una función booleana y cómo verificar si dos números son iguales. Sin embargo, no tengo idea de por dónde empezar representando la tabla hash como una función booleana. Además, conectar todas las piezas juntas me desconcierta.

¿Alguna idea? Ideas? ¿Colaboración? Me gustaría ver a dónde va esto.

Gracias de antemano.

Answer 1

La forma en que lo veo, el uso de BDDs, como se usa en este contexto, es simplemente una forma de representar y ayudar a manipular una expresión utilizada para evaluar, por ejemplo, si tu oración cumple los requisitos para ser un yo -enumerar pangram. Existen reglas para manipularlas de una manera conceptualmente más fácil que las de manipulación de enunciado en álgebra de Boole, porque son más fáciles de representar en esa notación que en la notación de Boole, del mismo modo que un polinomio en 8000 variables es más difícil de manejar. en su forma general que en alguna otra notación que representa de dónde viene y tal. Existen algoritmos informáticos para manipular cualquiera de esos cuatro, por lo que su mejor opción es, probablemente, buscar y adaptar uno a sus necesidades. Puede encontrar que this document es útil.

Google también puede ser útil para encontrar recursos adicionales.