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