Let's make a combination without duplication | First, calculate the total number

I am making a program that asks for a combination.

100C9 is trying to enumerate unique combinations with the largest pattern. First, the total number of patterns was calculated by processing using the usual recurrence formula.

Find the total number of nCr patterns using a recurrence formula

private static long calcNumOfCombination(int n, int r){
	r = Math.min(r, n - r);
	if (r == 1) {
		return n;
	}

	long sum = 1;
	for (int i = 1; i <= r; i++) {
		sum = sum * (n - i + 1) / i;
	}
	return sum;
}

//Total number of patterns when selecting 9 out of 100 elements
System.out.println(calcNumOfCombination(100, 9));

Execution result


1902231808400

How many digits? I don't know because I don't want to count. The purpose is not to list the combinations, After enumerating the data of this many patterns, we are doing something while doing the original processing.

The original process is easy, so I'm having a hard time listing them.

Of course, enumerating is super easy if you prepare a separate processing method for multiple loops of Gorigori for each selection number R given without using recursion, and switch the method to call according to the number of R. Yup. .. ..

I tried tail recursion in Java by imitating the appearance

It no longer falls even after recursive processing. I'm surprised.

Recommended Posts

Let's make a combination without duplication | First, calculate the total number
Whether the total product of the first n prime numbers plus 1 is a prime number
Find the remainder divided by 3 without using a number
Let's make a calculator application in Java ~ Display the application window
Let's make the app better
Let's make a custom_cop that points out the shaking of the name