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 an application where I iterate through all k-combinations of a set of size n. For example here I have listed all k-combinations for when n is 4. Also I have separated each list of combinations for k by a dashed line, and indexed them.

Now I want to optimize as I know that certain combinations do not need to be checked. For example, if I do not need to check any combination containing 1&3, I can remove index 1 from the second layer, and index 0 and 2 from the third layer, and index 0 from the last layer.

My question is, given that I know I don't need to check combinations containing 1&3, how can I find the indices of the combinations in each layer that do not need to be checked?

My hope is that I can do this without resorting to brute forcing.

Index: Combination
----------------------------------
0: 1
1: 2                   Layer k = 1
2: 3
3: 4
----------------------------------
0: 12
1: 13
2: 14                  Layer k = 2
3: 23
4: 24
5: 34
----------------------------------
0: 123
1: 124                 Layer k = 3
2: 134
3: 234
----------------------------------
0: 1234                Layer k = 4
share|improve this question
    
This can probably be solved, but are you sure you're asking the right question? Presumably you want to know the indices of combinations containing 1 and 3 so that when you step through the list of combinations, you can ignore them. Well, wouldn't it be easier not to generate those combinations in the first place when you're making the list? –  ShreevatsaR Jul 9 '11 at 12:42
    
True, but my application actually goes a little deeper. Basically, to generate the data for say layer 3, index 0, I use the data already generated at indices 0,1&3 in layer 2. (Only a maximum of 3 indices will need to be selected, even for larger combinations).So to do this I created a big LUT which would map layer 3 index 0 to indices (0,1,3) in layer 2. So to recreate this LUT each time would be very slow. –  Projectile Fish Jul 9 '11 at 13:00
add comment

2 Answers 2

up vote 1 down vote accepted

If you don't need to separate into layers, you can just regard your combinations as binary numbers of $n$ bits. You can then do an outer loop over the $2^{n-2}$ combinations that ignore $1$ and $3$, then do an inner loop over $0, 1, 2$ for the bits $1$ and $3$. This avoids the sets with both $1$ and $3$

If you do need to separate into layers, you can do something similar. For layer $k$, there are $\binom{n-2}{k}$ subsets that have $k$ items without $1$ and $3$. You can couple those with the $\binom{n-2}{k-1}$ subsets with $k-1$ items, each paired with $1$ and then paired with $3$. You can generate these subsets from the index as shown here.

share|improve this answer
add comment

Replace $3$ by $2$ and now count how many combinations do contain both $1$ and $2$. This will give a solution if you're really concerned only about a particular pair.

You can also solve the general problem using this idea of counting, but it gets a bit messier.

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.