0
$\begingroup$

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 
  • 0
    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.2011-07-09

2 Answers 2

1

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.

0

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.