# 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

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7937541007995605, "perplexity": 256.47495802695926}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-18/segments/1429246635639.11/warc/CC-MAIN-20150417045715-00101-ip-10-235-10-82.ec2.internal.warc.gz"}