# Formalize as combinatorics problem (get all sets that boolean sum == (1,1,1))

I have such a problem: there are several boolean tupels (properties of some objects)

K1 = (0, 1, 0)
K2 = (1, 1, 0)
K3 = (1, 1, 0)
K4 = (0, 0, 1)
K5 = (0, 0, 1)


I need to get all possible combinations, such that boolean sum of elements == (1, 1, 1), e.g.

N = [(K1, K2, K4), (K1, K3, K4), (K1, K2, K5),
(K1, K3, K5), (K2, K4), (K2, K5), (K3, K4), (K3, K5), ...,
(K1, K2, K3, K4, K5)]


So the questions are:

1. Can be this problem formalized as combinatorics problem?
2. Are there any usefull functions in numpy, scipy (Python) to solve this problem?

I belive if I get formalization of this problem I'll be able to solve by programming.

Thank you very much for your attention!

-
I think that stackoverflow would be a better place for this question... –  Belgi Jun 10 '12 at 11:38
Why is (K1,K2,K3,K4,K5) not in your list of N? –  Henry Jun 10 '12 at 11:38
Henry, sorry I didn't quite fully described problem. I want to have as little as possible of repetitive elements, that have 1 on same position. –  Dimitry Jun 10 '12 at 11:41
Henry, sorry again!) I've decided that it's not so important to have lots of repetitive elements, couse their summed reliability (additional properties out of the question scope) will be lower anyway. –  Dimitry Jun 10 '12 at 11:47
Belgi, I want to get some sort of formula that might be useful in math representation of algorithm –  Dimitry Jun 10 '12 at 11:49

## 1 Answer

This is more of a linear algebra problem than combinatorics.

Here $V=\mathrm{span}(K_1,K_2,\ldots,K_n)$ forms a subspace of the vector space $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \cdots \mathbb{Z}_2$. The size of $V$ is $2^r$, where $r$ is the rank of the matrix; in this case: $\left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array} \right).$

Every element in $V$ can be generated in the same number of ways (i.e. the same number of linear combinations of $\{K_1,K_2,\ldots,K_n\}$. Thus:

Claim: If $(1,1,\ldots,1) \in V$, then it can be generated in $2^n/2^r$ ways. (Otherwise $0$ ways.)

You can find the solutions explicitly by solving the system of equations:

$\left( \begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ \end{array} \right)=\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ \end{array} \right).$ You'll end up with some free variables (which may take either value $0$ or $1$), and the remaining variables will be determined from them.

There's a gazillion linear algebra packages out there, or you could write your own for this specialised problem (I'll leave that to you).

-