I have a large collection of lists consisting of 1's and 0's, each list the same length. I call each list a row.
I want to know the number of ways to select rows such that their cumulative OR results in all 1's. In other words, the number of ways to choose rows where at least one 1 exists in each column somewhere.
I am having trouble doing this efficiently. Right now I am using inclusion exclusion. The number of ways to choose rows with at least one 1 in each column is equal to the number of ways to select any subset of rows minus the number of ways to select no 1's in a column, or all 0's.
But I am having trouble taking this all the way because it requires being able to efficiently determine which rows have 0's in specific indices.
I found this paper http://cs-people.bu.edu/evimaria/papers/kdd127-gionis.pdf which indicates that your problem is indeed #P-complete, (if you look at it as a set-cover problem, which is easy to do, your 0 and 1 just say whether the given index is in the subset encoded by the row, and you want to cover all indices with a choice of subsets, i.e. rows), and hence, although there may be some heuristics to speed up counting (I haven't done enough reading to see if there are), you most likely can't find a polynomial time algorithm to count your number of solutions. The paper indicates some statistical approximation approaches though.