-2

I have spent a couple of minutes recreating the formula nCr = n!/r!(n-r)! to find the number of combinations in an array. So far I have been succesful in implementing this formula, but I'm seeking alternative methods of using such a formula. Here is my code:


import java.util.Scanner;

public class Factorial {

    public static void main(String[] args) {
        System.out.println("Enter Num");
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        long f = 1;
        for(int i = 1; i <= num; ++i)
        {
            f *= i;
        }
        System.out.println("Factorial of " +num +" = " +f);
        System.out.println("Enter r");
        int r = sc.nextInt();
        int bracket = num-r;
        int f2 = 1;
        int rf = 1;
        for(int i = 1; i <= r; ++i)
        {
            rf *= i;
        }
        for(int i = 1; i <= bracket; ++i)
        {
            f2 *= i;
        }
        long ans = f/(rf*f2) ;
        System.out.println(num+"C"+r +" = "+ans);
    }
}
Simon Moyana
  • 11
  • 1
  • 1
    You keep repeating that looped multiplication: use a method. – Andy Turner Nov 17 '20 at 17:34
  • Simon, this is a good start. You'll find that computing nCr via n!/(r! (n - r)!) runs into problems when is larger than 12, because factorials quickly become very large numbers. Another approach is to write out the factorials and cancel common terms, which will allow you to handle somewhat larger n. Still other approaches are needed to go farther. Good luck and have fun, this is a good problem. – Robert Dodier Nov 17 '20 at 19:43
  • 1. `n!/r!` is `n!` without the first `r` multiplications so instead of dividing just skip them 2. You need to keep the sub results as small as possible to avoid integer overflow so You need to do this in single loop and when both dividends `a,b` from `a/b` are divisible by the same value divide them... The simplest is to test least signifficant bit is zero. If it is divide by 2 (or bitshift right) ... if you want something better test divisibility by few first primes... 3. use unsigned variables that will give you one more bit ... – Spektre Nov 19 '20 at 09:03
  • see [compute nCr in C++](https://stackoverflow.com/a/64910565/2521214) – Spektre Nov 19 '20 at 11:17

1 Answers1

1

A great way to improve your formule is by using recursion. You can replace your loops with this recursive method:

static int factorial(int n){
    return n == 0 ? 1 : n * factorial(n-1);
}
Laugslander
  • 386
  • 2
  • 16
  • 1
    Using recursion for this is not a great idea, at least in Java. It will be terribly slow, compared to a plain old loop. – Andy Turner Nov 17 '20 at 17:36
  • 1
    @AndyTurner There isn't any problem with efficiency here, or, for that matter, any problem with stack overflow. The largest factorial which can be represented by a signed 32 bit integer is 12!. Beyond that one has to start thinking about alternatives which are pretty far beyond introductory programming. The recursive definition is a very clear expression of the mathematical formulation so for that reason it should be preferred for beginners. – Robert Dodier Nov 17 '20 at 18:05