A Specific Combination

This code is going to be included in my Minesweeper Probabilities project. (so far it only exists on the develop-branch)

The purpose is to return a specific combination, let's say for example that you have 7 elements and want to return 3 of them, simple combinatorics tells us that there are \$\binom{7}{3} = \frac{765}{321} = 35\$ combinations to do this, so let's say that we want to return an arbitrary combination, let's say combination number \$20\$.

So we have to decide the order for the combinations. Let's take the elements [0 1 2 3 4 5 6], the order that felt the most natural to me is:

012 013 014 015 016
023 024 025 026
034 035 036
045 046
056

123 124 125 126
134 135 136
145 146
156

234 235...

So when we have written these, we can see that 134 is the 20th combination.

But without actually writing them all down, how can we come to the conclusion that 134 is the 20th combination?

There are \$\binom{6}{2} = 15\$ combinations where \$0\$ is the first number. As \$20 > 15\$, we know that 0 is not the first number. So we reduce 20 by 15, increase the nextNumber variable and continue.

Then we have nextNumber == 2 and combination == 5, as there are \$\binom{5}{2}\$ combinations where \$1\$ is the first number, we know that 1 is the first number, reduce the remainingSize and continue on our way...

Then there are 4 combinations were 2 is the next number [123, 125, 126, 127], but as 5 > 4, 2 is not the next number. So again we reduce the combination we're looking for (5) by the number of combinations for 2 being the next number (4), so we get combination = 1 and also increase nextNumber to 3.

Now, as combination == 1 the remaining numbers are 3 and 4.

I hope the code is pretty self-explanatory.

Code

As I need to support very big combinations, such as \$\binom{256}{51} = 2.034*10^{54}\$, I assumed that double will not have enough precision, so I went with BigInteger. I hope this doesn't cause too much impact on performance th

A significant part of the algorithm is to compute the binomial coefficients

while (remainingSize > 0) {
    BigInteger ncr = nCrBigInt(remainingElements - 1, remainingSize - 1);
    // ...
}

However, in each loop iteration, either

• remainingElements is decremented, or

• both remainingElements and remainingSize are decremented,

which means that you can take advantage of the following
identities for binomial coefficients:

C(n-1, k-1) = C(n, k) * k / n
 C(n-1, k)   = C(n, k) * (n - k) / n

and compute the next value of ncr from the previous value, instead
of calling nCrBigInt() again. That is one multiplication and division
instead of min(k, n-k).

StackExchange Code Review Q#62194, answer score: 6