Cómo calcular el cierre de un conjunto de cadenas binarias en el término de la "Y" y "O" los operadores?

Question

Dado un conjunto de $n$ cadenas binarias de longitud $m$, ¿cuántas cadenas binarias, al menos, debemos agregar al conjunto para asegurarse de que el archivo binario "Y" y "O" los operadores están cerrados en el set? La salida del problema es el número de cadenas binarias necesarias para agregar.

Por ejemplo, dado el conjunto {001, 010, 110}, al menos deberíamos agregar {000, 011, 111} al conjunto para hacer tanto "Y" y "O" los operadores cerrado. De modo que el resultado es 3.

Hay alguna buena algoritmo o idea relacionada con el problema? Muchas gracias.

Answer 1

Creo que están tratando de calcular el "sublattice de la booleano entramado de longitud m", generados por la n cadenas binarias. No sé una manera rápida de calcular sublattices. En general, es exponencial en n.

Aquí está un ejemplo: Para cualquier entero positivo n, y cualquier entero positivo m ≥ n, inicie con las cadenas binarias de longitud m, que son cero en la posición i para todo i > n, y que son distintos de cero en todos, pero uno de otro lugar. Hay exactamente n tales cadenas. Cuántas cadenas tienes que añadir? 2ⁿ−n, ya que cada cadena con exactamente un valor distinto de cero de la entrada (en las primeras n posiciones) es un a de n−1 de la inicial de las cadenas. Esta salida es exponencial, de longitud n.

---

Si usted incluyó "no" o incluidos de otra manera, "xor", que pronto iba a actualizar a la búsqueda de "los ideales en el álgebra de boole" y esto se convierte en álgebra lineal, y cosas como la eliminación gaussiana debe hacer que el problema cuadrática en n.

Por supuesto, la salida de sí mismo podría todavía ser exponencial en n, por lo que tendrá que conformarse con una diferente, pero muy útil, tipo de salida: una base.

---

Como señala Ross Millikan, el problema crítico para una solución práctica es un mejor tipo de datos para la salida. Solo el listado de todas las palabras que va a ser exponencial en general, pero a veces uno podría producir ridículamente rápido pertenencia a funciones de prueba (y producto de ellos ridículamente rápido) - en mi ejemplo, la función de pertenencia simplemente comprueba que las posiciones de n+1 a m son todos 0.

Sin embargo, no hay datos-tipo de trabajo de magia. Dependiendo de cómo muchas respuestas posibles que hay, el tipo de datos tendrá que ser al menos de un cierto tamaño. Queyranne–Tardella (2008) intento de responder a la pregunta de cuántos sublattices están ahí y, de hecho, el estudio de exactamente el problema original. Ellos proporcionan un tipo de datos para la salida y demostrar que es la memoria óptima de hasta un factor constante:

Queyranne, Maurice; Tardella, Fabio. "Sublattices de producto de espacios: cascos, representaciones y contar." La Matemática Discreta. 308 (2008), no. 9, 1508-1523. MR2392592 DOI:10.1016/j.disco.2007.03.080

Answer 2

Usted puede buscar para los casos donde uno de los bits implica la otra. En su ejemplo, el bit 2 (MSB) implica el bit 1-no hay ejemplos en su conjunto dado con bit 2 bit 1 off. Así que usted nunca puede deshacerse de este y 100 y 101 no será necesario. Esto es $n^2m$ en la complejidad

Añadido en respuesta a comentario: Usted está buscando para los casos en los que el bit $i$ en todas tus palabras siempre bits $j$. Así que usted podría hacer una matriz $m \times m$ e inicializarla a todos los $1$. Ir a través de todos los $n$ entrada de palabras. Para cada palabra, compruebe si el bit i=0 y el bit j=1. Si es así, ajuste el $(i,j)$ elemento $0$. Al final, si alguna de las entradas de la matriz son todavía $1$, después de haber bits $j$ sobre los medios para asegurarse de bits $i$ es en su entrada de palabras. Como Y y O no puede destruir esto, ninguno de su salida de palabras se han$i$$j$. Como chequear $m(m-1)/2 \approx m^2$ bits en $n$ entrada de palabras, esto es de orden $m^2n$