Permutation and Combination in Java

In mathematics, Permutation and Combination are two important concepts. Permutation is the different arrangements of the set elements. The arrangements can be made by taking one element at a time, some element at a time and all elements at a time. Combination is the different selections of the set of elements taken one by one, or some, or all at a time. In Java, the definition of Permutation and Combination is the same.

For example, if we have a set having only two elements, X and Y. The permutation value will be 2 because only two arrangements are possible, i.e., XY and YX. The combination value will be 1 because only one way to select two elements, i.e., selecting both of them together.

Permutation

In Java, it is very easy to get all the permutations and the permutation value of an array, list, or set. For getting the permutation value programmatically in Java, we use the following formula:

Let’s first take an example of Permutation to understand how we can get the permutation value programmatically in Java.

PermutationExample.java

Output:

Description

In the above code, we create a class PermutationExample to get the permutation value. In the PermutationExample class, we create a static method fact() for calculating the factorial. In the permutation formula, we need to calculate the factorial of n and n-r. In the main method, we create a list of numbers and add certain elements to it. We use the size() method to get the number of elements in the list. We set a constant value 3 to r, i.e., the number of items taken for the Permutation. After that, we use the permutation formula, i.e., fact(n)/fact(n-r) and store the result into the result variable. At last, we show the final result to the users.

We can not only find the permutation value, but also we can get all the permutations of the array. Let’s take one more example of Permutation to get all the possible Permutation of an array element.

GetAllPermutations.java

Output:

Description

The above code uses recursion to get all Permutation, so it can be a little bit difficult to understand. In the above code, we create GetAllPermutation class to get all the Permutation of the array. We create a static method getPermutations(), and inside this method, we call the helper() method. In the helper method,

1. We first check the position to ensure whether the position indicates the last element or not. If the position indicates the last element, then there will be nothing to permute. In this case, we print all the array elements and pass the control to the main() method.
2. If the position doesn’t indicate the last element of the array, we swap the indices position elements and i.
3. After swapping the elements, we perform the recursion on the sub-array array[position+1….end].
4. After that, we swap the elements back to get all the Permutation of the array.

Combination

Just like permutation value, getting combination value is very easy in Java but to get all the combination of array, list, and set elements is more difficult than getting permutations. For getting the combination value programmatically in Java, we use the following formula:

Let’s first take an example of Combination to understand how we can get the combination value programmatically in Java

CombinationExample.java

Output:

Description

In the above code, we create a class CombinationExample for getting the combination value. In the CombinationExample class, we create a static method fact() to calculate the factorial. In the combination formula, we need to calculate the factorial of n, r and n-r. In the main method, we create a list of numbers and add certain elements to it. We use the size() method to get the number of elements in the list. We set a constant value 2 to r, i.e., the number of items being chosen at a time. After that, we use the combination formula, i.e., fact(n) / (fact(r) * fact(n-r)) and store the result into the result variable. At last, we show the final result to the users.