Suppose I have a basis $v_1, ..., v_n$ of boolean vectors and a boolean vector $v$ that was constructed by iterated $v = v_i$ $OR$ $v_j$ statements. I want a way to figure our how many unique combinations $v_I$, $I = \alpha_1,...,\alpha_k$, $\alpha_i \neq \alpha_j \forall i \neq j$ there are that, when union/or'd, yield $v$. The only thing I know about the basis vectors is that each basis vector has an entry that is true only for that basis vector, and false for all other basis vectors (note then that the vector $(TRUE,...,TRUE)$ has exactly one representation). The order of the basis vectors does not matter - I treat $v_i$ $OR...OR$ $v_j$ and $v_j$ $OR...OR$ $v_i$ equally. An analytic method is preferred but a polynomial-time algorithm would be great too. A polynomial-time algorithm for an upper bound for the number of basis representations (over the whole space) would be incredible, but if someone answered the main question I could probably do that on my own or with an optimization suite.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
For each i, let S(i) be the index of the bit that is set only in the i'th basis vector v_i
If V is the result of orring together some subset T of basis vectors, then for each i, the S(i)'th bit is set in V iff v_i is in T.
So for any vector V there is at most one such representation.