Permutation Coefficient in Java
Permutation can be defined as, the process of arranging all the members of a given set to form a sequence. The permutation coefficient is represented by P(n, r). It gives the number of permutations of n elements taking r at a time. Thus, if we have to find the P(5, 2), then it means there are 5 elements (n = 5), and one can take any 2 elements from it (r = 2), and the task is to find the number of ways one can take those 2 elements. In this section, we will discuss the permutation coefficient and how to calculate it. Also, we will create a Java program for the same.
Suppose, those 5 elements are 1, 2, 3, 4, and 5, and the 2 elements we can take are:
(1, 2) (1, 3) (1, 4) (1, 5)
(2, 1) (2, 3) (2, 4) (2, 5)
(3, 1) (3, 2) (3, 4) (3, 5)
(4, 1) (4, 2) (4, 3) (4, 5)
(5, 1) (5, 2) (5, 3) (5, 5)
If we count the mentioned pairs, we get 20. Thus, there are 20 ways one can select those 2 elements from the set of 5 elements (1, 2, 3, 4, 5).
Mathematically, we can compute the value of P(n, r) by using the following formula:
Thus,
P(5, 2) = 5! / (5 – 2)! = 5! / 3! = (5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 120 / 6 = 20
P(7, 4) = 7! / (7 – 4)! = 7! / 3! = (7 x 6 x 5 x 4 x 3 x 2 x 1) / (3 x 2 x 1) = 5040 / 6 = 840
Note:
- The value of P(n, r) is always 1, for r = 0.
P(n, 0) = n! / (n – 0)! = n! / n! = 1 - The value of P(n, r) is always n!, for r = n.
P(n, n) = n! / (n – n)! = n! / 0! = n! / 1 = n! (0! is always 1)
Implementation
Let’s compute the value of P(n, r) through a Java program.
Using Array
FileName: PermCoefficient.java
Output:
The value of (7, 4) is: 840 The value of (5, 2) is: 20
Time-complexity: The time complexity of the above program is O(n + r). It is because the for-loop mentioned in the method findFactorial() runs twice: one for the value n and another for the value of r.
Another Approach
The other way to find the value of P(n, r) is mentioned below.
P(n, r) = P(n – 1, r) + r x P(n – 1, r – 1)
If n < r, then P(n, r) = 0
and
P(n, 0) = 1
&
P(n, n) = n!
&
P(n, 1) = n
Thus,
P(10, 2) = P(10 – 1, 2) + 2 x P(10 – 1, 2 – 1)
P(10, 2) = P(9, 2) + 2 x P(9, 1)
P(10, 2) = P(9, 2) + 2 x 9 = P(9, 2) + 18 – Equation A
Now, we will calculate the value of P(9, 2)
P(9, 2) = P(9 – 1, 2) + 2 x P(9 – 1, 2 – 1)
= P(8, 2) + 2 x P(8, 1) – Equation B
= P(8, 2) + 2 x 8 = P(8, 2) + 16
P(8, 2) = P(8 – 1, 2) + 2 x P(8 – 1, 2 – 1)
= P(7, 2) + 2 x P(7, 1)
= P(7, 2) + 2 x 7 = P(7, 2) + 14 – Equation C
P(7, 2) = P(7 – 1, 2) + 2 x P(7 – 1, 2 – 1)
= P(6, 2) + 2 x P(6, 1)
= P(6, 2) + 2 x 6 = P(6, 2) + 12 – Equation D
P(6, 2) = P(6 – 1, 2) + 2 x P(6 – 1, 2 – 1)
= P(5, 2) + 2 x P(5, 1)
= P(5, 2) + 2 x 5 = P(5, 2) + 10 – Equation E
P(5, 2) = P(5 – 1, 2) + 2 x P(5 – 1, 2 – 1)
= P(4, 2) + 2 x P(4, 1)
= P(4, 2) + 2 x 4 = P(4, 2) + 8 Equation F
P(4, 2) = P(4 – 1, 2) + 2 x P(4 – 1, 2 – 1)
= P(3, 2) + 2 x P(3, 1)
= P(3, 2) + 2 x 3 = P(3, 2) + 6 Equation G
P(3, 2) = P(3 – 1, 2) + 2 x P(3 – 1, 2 – 1)
= P(2, 2) + 2 x P(2, 1)
= 2! + 2 x 2 = 2 x 1 + 2 x 2 = 2 + 4 = 6
Using the value of P(3, 2) in equation G, we get
P(4, 2) = P(3, 2) + 6 = 6 + 6 = 12
Using the value of P(4, 2) in equation F, we get
P(5, 2) = P(4, 2) + 8 = 12 + 8 = 20
Using the value of P(5, 2) in equation E, we get
P(6, 2) = P(5, 2) + 10 = 20 + 10 = 30
Using the value of P(6, 2) in equation D, we get
P(7, 2) = P(6, 2) + 12 = 30 + 12 = 42
Using the value of P(7, 2) in equation C, we get
P(8, 2) = P(7, 2) + 14 = 42 + 14 = 56
Using the value of P(8, 2) in equation B, we get
P(9, 2) = P(8, 2) + 16 = 56 + 16 = 72
Using the value of P(9, 2) in equation A, we get
P(10, 2) = P(9, 2) + 18 = 72 + 18 = 90
Recursive Approach
Let’s see the implementation of it using recursion.
FileName: PermutationCoeff.java
Output:
The Value of P(10, 2) is: 90 The Value of P(7, 3) is: 210
Iterative Approach-1
Let’s see the implementation of it using nested for-loops and two-dimensional array.
FileName: PermutationCoeff1.java
Output:
The Value of P(10, 2) is: 90 The Value of P(7, 3) is: 210
In the above program, we have used the nested for-loops for computing the value of P(n, r). Because of the nested for-loops, the time complexity of the above program is O(n * r). The space complexity is also O(n * r). However, we can do the optimization and reduce the time as well the space complexity to O(n).
Iterative Approach-2
Let’s see the implementation in which we have used a single for-loop and one-dimensional array.
FileName: PermutationCoeff2.java
Output:
The Value of P(10, 2) is: 90 The Value of P(7, 3) is: 210
We can further do the optimization and reduce the space complexity to O(1). However, the time complexity still remains the same, which is O(n). Observe the following program.
Iterative Approach-3
Let’s see the implementation of it using a single for-loop.
FileName: PermutationCoeff3.java
Output:
The Value of P(10, 2) is: 90 The Value of P(7, 3) is: 210