По формуле: n! / ((N-k)! * K!)
Если мы просто вычисляем числитель и знаменатель, многие вычисления будут потрачены впустую, и, возможно, диапазон «int», «float» или даже «BigInteger» может заполниться.
Таким образом, чтобы преодолеть этот сценарий, мы можем отменить все до того, как умножим значения.
предположим, что n = 6, k = 3
что означает => 6 * 5 * 4 * 3 * 2 * 1 / ((3 * 2) * (3 * 2))
предположим, что если мы умножим числитель, диапазон может заполниться. Лучший вариант - отменить его, прежде чем даже умножить значения.
В этом случае ->
если мы отменим все, что у нас осталось:
(2 * 5 * 2)
умножение этих значений намного проще и потребует меньше вычислений.
=============================================== =======
Приведенный ниже код будет работать "эффективно" для чисел, где:
- n == k
- k
- k == 0
- разница между n и k слишком велика, например.
n = 1000, k = 2
- k = n / 2 (САМОЕ ПРОЧНОЕ)
- Значение k близко к половине
значение n
Возможно, код еще можно улучшить.
BigInteger calculateCombination(int num, int k) {
if (num == k || k == 0)
return BigInteger.ONE ;
int numMinusK = num - k;
int stopAt; // if n=100, k=2 , can stop the multiplication process at 100*99
int denominator;
// if n=100, k=98 OR n=100, k=2 --> output remains same.
// thus choosing the smaller number to multiply with
if (numMinusK > k) {
stopAt = numMinusK;
denominator = k;
} else {
stopAt = k;
denominator = numMinusK;
}
// adding all the denominator nums into list
List<Integer> denoFactList = new ArrayList<Integer>();
for (int i = 2; i <= denominator; i++) {
denoFactList.add(i);
}
// creating multiples list, because 42 / 27 is not possible
// but 42 / 3 and followed by 42 / 2 is also possible
// leaving us only with "7"
List<Integer> multiplesList = breakInMultiples(denoFactList);
Collections.sort(multiplesList, Collections.reverseOrder());
Iterator<Integer> itr;
BigInteger total = BigInteger.ONE;
while (num > 0 && num > stopAt) {
long numToMultiplyWith = num;
if (!multiplesList.isEmpty()) {
itr = multiplesList.iterator();
while (itr.hasNext()) {
int val = itr.next();
if (numToMultiplyWith % val == 0) {
numToMultiplyWith = numToMultiplyWith / val;
itr.remove();
}
}
}
total = total.multiply(BigInteger.valueOf(numToMultiplyWith));
num--;
}
return total;
}
ArrayList<Integer> breakInMultiples(List<Integer> denoFactList) {
ArrayList<Integer> multiplesList = new ArrayList<>();
for (int i : denoFactList)
updateListWithMultiplesOf(multiplesList, i);
return multiplesList;
}
void updateListWithMultiplesOf(ArrayList<Integer> list, int i) {
int count = 2;
while (i > 1) {
while (i % count == 0) {
list.add(count);
i = i / count;
}
count++;
}
}