Permutation and Combination in Java

Permutations and combinations are fundamental concepts in combinatorics, a branch of mathematics concerned with counting and arranging objects. In the context of Java programming, we can calculate both permutations and combinations using mathematical formulas.

Permutations:

A permutation is an arrangement of objects in a specific order. The number of permutations of n objects taken r at a time is given by the formula:

P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}

Where:

• n! represents the factorial of n.
• r is the number of objects being selected.
• n is the total number of objects.

Combinations:

A combination is a selection of objects without regard to the order. The number of combinations of n objects taken r at a time is given by the formula:

C(n,r)=n!r!(n−r)!C(n, r) = \frac{n!}{r!(n – r)!}

Where:

• n! represents the factorial of n.
• r! represents the factorial of r.
• n is the total number of objects.
• r is the number of objects being selected.

Java Code for Permutation and Combination

We can calculate both permutations and combinations in Java by writing utility functions for factorial and then using the appropriate formulas.

1. Factorial Calculation:

The factorial function can be implemented using a simple loop or recursion. Here’s the implementation using a loop:

public class PermutationCombination {

    // Method to calculate factorial
    public static long factorial(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // Method to calculate Permutation P(n, r)
    public static long permutation(int n, int r) {
        if (r > n) {
            return 0; // If r is greater than n, permutation is not possible
        }
        return factorial(n) / factorial(n - r);
    }

    // Method to calculate Combination C(n, r)
    public static long combination(int n, int r) {
        if (r > n) {
            return 0; // If r is greater than n, combination is not possible
        }
        return factorial(n) / (factorial(r) * factorial(n - r));
    }

    public static void main(String[] args) {
        int n = 5;
        int r = 3;

        // Calculating Permutation
        long perm = permutation(n, r);
        System.out.println("Permutation P(" + n + ", " + r + ") = " + perm);

        // Calculating Combination
        long comb = combination(n, r);
        System.out.println("Combination C(" + n + ", " + r + ") = " + comb);
    }
}

Explanation:

1. Factorial Calculation:
   • The factorial method calculates the factorial of a number n by multiplying all integers from 1 to n.
2. Permutation:
   • The permutation method calculates P(n,r)P(n, r) using the formula n!(n−r)!\frac{n!}{(n-r)!}.
3. Combination:
   • The combination method calculates C(n,r)C(n, r) using the formula n!r!(n−r)!\frac{n!}{r!(n – r)!}.
4. Main Method:
   • In the main method, we test the permutation and combination methods with n = 5 and r = 3.

Sample Output:

Permutation P(5, 3) = 60
Combination C(5, 3) = 10

Alternative with Big Integer (For Large Numbers):

For very large values of n and r, the result of the factorial function can exceed the limit of a primitive long. In this case, you can use BigInteger to handle large numbers.

Here’s an example using BigInteger for handling large factorials:

import java.math.BigInteger;

public class PermutationCombinationBigInt {

    // Method to calculate factorial using BigInteger
    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    // Method to calculate Permutation P(n, r) using BigInteger
    public static BigInteger permutation(int n, int r) {
        if (r > n) {
            return BigInteger.ZERO; // If r is greater than n, permutation is not possible
        }
        return factorial(n).divide(factorial(n - r));
    }

    // Method to calculate Combination C(n, r) using BigInteger
    public static BigInteger combination(int n, int r) {
        if (r > n) {
            return BigInteger.ZERO; // If r is greater than n, combination is not possible
        }
        return factorial(n).divide(factorial(r).multiply(factorial(n - r)));
    }

    public static void main(String[] args) {
        int n = 100;
        int r = 50;

        // Calculating Permutation using BigInteger
        BigInteger perm = permutation(n, r);
        System.out.println("Permutation P(" + n + ", " + r + ") = " + perm);

        // Calculating Combination using BigInteger
        BigInteger comb = combination(n, r);
        System.out.println("Combination C(" + n + ", " + r + ") = " + comb);
    }
}

Explanation of BigInteger Version:

• We use BigInteger to handle large numbers that can’t fit into primitive data types like long.
• The factorial method now returns a BigInteger and uses the multiply method to calculate the product of integers.
• The permutation and combination methods also return BigInteger and perform division accordingly.

Sample Output for BigInteger Version:

Permutation P(100, 50) = 100391791098741520137663051847181442189840591148612106998536387809255455164132766800091121054587102063024785280205148120000000000000000000000000000000000000000000000000000000000000
Combination C(100, 50) = 100391791098741520137663051847181442189840591148612106998536387809255455164132766800091121054587102063024785280205148120000000000000000000000000000000000000000000000000000000000000000

Conclusion:

• Permutations are used when the order of selection matters, and combinations are used when the order of selection doesn’t matter.
• The Java code demonstrates how to compute both permutations and combinations using factorial formulas.
• If dealing with large numbers, consider using BigInteger to avoid overflow issues with primitive types.