Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.