0
$\begingroup$

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!

  • 0
    Belgi, I want to get some sort of formula that might be useful in math representation of algorithm2012-06-10

1 Answers 1

0

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).