[Enhancement] Combinations

[kumanoit]

File: Combinations.java file under Maths package
nCk is calculated as (n!)/((k!)(n - k)!)

• The above method can exceed limit of long when factorial(n) is larger than limits of long variable.
• Thus even if nCk is within range of long variable above reason can lead to incorrect result.
• Also since it is creating factorial considering all n values, it will be slow.
• This is an optimized version of computing combinations.
• Observations:
• nC(k + 1) = (n - k) * nCk / (k + 1)
• We know the value of nCk when k = 1 which is nCk = n
• Using this base value and above formula we can compute the next term nC(k+1)

Note:
The optimized version will also fail at a point when the input is too big which can't be saved in long.

[kumanoit]

I am interested in this.

[siriak]

Isn't it the same formula, just recursive? I don't see a benefit of the proposed approach

[kumanoit]

This is what is there presently

 {
    return factorial(n) / (factorial(k) * factorial(n - k));
  }

In the above implementation,(n!) will be computed first which will take O(n) time and similarly (k!) and (n-k)! will be calculated. Total computations will take time like O(n) + O(k) + O(n - k)
Secondly, Calculating whole factorial and saving it in long variable will overflow the range of long variable.

The iterative solution that I proposed will reduce the computation. Since it is calculating next term from previous term it won't take that long and also the solution will be in range of long.
Please take a look at below method.

  public static long combinationsOptimized(int n, int K) {
    // nC0 is always 1
    long solution = 1;
    for(int k = 0; k < K; k++) {
      long next = (n - k) * solution / (k + 1);
      solution = next;
    }
    return solution;
  }

The above loop will run only k times thus leading to O(k) time complexity.

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions]

Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!