Número de maneras de elegir filas con la condición de inclusión

Question

Tengo una gran colección de listas que consta de 1's y 0's, cada una de las listas de la misma longitud. Yo llame a cada lista una fila.

Quiero saber el número de formas de seleccionar las filas de tal manera que su acumulativa O resultados en todos los 1. En otras palabras, el número de maneras de elegir las filas en las que al menos un 1 existe en cada columna en algún lugar.

Estoy teniendo problemas para hacer esto de manera eficiente. Ahora mismo estoy usando la inclusión a la exclusión. El número de formas de elegir filas con al menos un 1 en cada columna es igual al número de formas de seleccionar un subconjunto de filas menos el número de formas de seleccionar no 1 en una columna, o todos 0.

Pero estoy teniendo problemas para tomar todo el camino porque se requiere ser capaz de determinar de manera eficiente las filas que tienen 0 en específicos de los índices.

Answer 1

He encontrado este papel http://cs-people.bu.edu/evimaria/papers/kdd127-gionis.pdf que indica que el problema es, de hecho, #P-completo, (si usted lo mira como un conjunto de la cubierta de problema, que es fácil de hacer, sus 0 y 1 acaba de decir que si el índice dado es en el subconjunto codificada por la fila, y se desea cubrir todos los índices, con una selección de subconjuntos, es decir, filas), y por lo tanto, aunque puede haber algunas heurísticas para acelerar el conteo (no he hecho lo suficiente a leer para ver si hay), lo más probable es que no se puede encontrar un polinomio de tiempo del algoritmo para contar su número de soluciones. El documento indica algunos aproximación estadística enfoques, aunque.