# Subset counting algorithm

I have a following problem i want to solve efficiently :

Input: Set s of {Pass,Fail}^k vectors, m - minimum percent of vectors

Output : Set of Sets of indexes: Where each set Contains indexes of Pass word in given vectors, and number of vectors that contains Pass in those indexes is over m percent from total vectors.

Example: {(Pass,Fail,Pass,Fail),(Pass,Fail,Pass,Pass)} where k is 4 and number of set elements is 2 and m 60% , output will be {{0,2},{0},{2}}

The output is group of sets where every set contains vector indexes that for at least 60% of vectors value was Pass

• Could you clarify what the output is? At present, it's very hard to understand. For example, what does `{1,2}` in your example correspond to? Aug 14 '11 at 12:23
• I am confused about the example -- the way I read your question, the output would be [ #2 ( 0, 2, 3 ) ], where #2 indicates the list of indices is from the second set. The first set fails because only 50% of the tests Pass. How does {{0,2},{0},{2}} convey this information? Note -- I assumed 0-based indexing for the set elements. Aug 14 '11 at 16:48
• Questions about algorithm design are on-topic here.
– user8
Aug 14 '11 at 18:41

This should give you the indices. The next step is to construct the power set out of these.

``````s = ((True,False,True,False),(True,False,True,True))