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