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