Entringer Number in Java
Combinatorial numbers that count specific kinds of permutations are known as the Entringer numbers. They specifically stand for the quantity of permutations of the set {1, 2,..., n + 1} that begin with k + 1.
There is a zigzag pattern to these permutations; they fall at first, then rise and fall again.
Example 1:
Input: n = 4, k = 2
Output : E(n,k) = 4
Explanation: The number of {1, 2, 3, 4, 5} permutations that begin with 3 is what we are looking for.
The following combinations are allowed: {[3 1 4 2 5],[ 3 2 4 1 5], [3 2 5 1 4], [3 1 5 2 4]}
As a result, E(4, 2) = 4.
Example 2:
Input: n =4 , k = 3
Output: E(n,k) = 5
Explanation: The number of {1, 2, 3, 4, 5} permutations that begin with 4 is what we are looking for.
The following combinations are allowed: {[4 5 2 3 1],[ 4 5 1 3 2], [4 3 5 1 2], [4 2 1 5 3], [4 1 5 2 3]}
As a result, E(4, 3) = 5.
Approach: Using Dynamic Programming
The code uses a dynamic programming approach to calculate the Entringer number E(n, k), a combinatorial number that counts the number of permutations of [n] where no integer appears in its natural position. It initializes an array `dp` of size `n+1`, iterates from `i = 1` to `n`, and updates the `dp` array to the values in `currentArray`. The final result is the Entringer number for the specified values of `n` and `k`. This bottom-up dynamic programming approach efficiently computes the desired result.
Here’s the implementation of finding the entringer number using the approach :
FileName: EntringerNumber.java
import java.util.Arrays;
public class EntringerNumber {
// Return Entringer Number E(n, k)
public static int calculateZigzagNumber(int n, int k) {
// array to store values
int[] dp = new int[n + 1];
Arrays.fill(dp, 0);
// Base cases
dp[0] = 1;
// iterate to get the current value from the previous value
for (int i = 1; i <= n; i++) {
int[] currentArray = new int[n + 1];
Arrays.fill(currentArray, 0);
for (int j = 1; j <= i; j++) {
currentArray[j] = currentArray[j - 1] + dp[i - j];
}
// assigning values to iterate further
dp = currentArray;
}
return dp[k];
}
public static void main(String[] args) {
int n = 4, k = 2;
System.out.println(calculateZigzagNumber(n, k));
}
}
Output:
4
Complexity analysis: The code has a time complexity of O(n^2) due to constant-time operations in the inner loop and a space complexity of O(n) due to the `dp` and `currentArray` arrays. It uses dynamic programming to calculate Entringer numbers, but the time complexity is quadratic due to nested loops.
Approach: Using Recursion
The code uses a recursive method to calculate the Entringer number E(n, k). It starts with base cases to handle special situations. Then, it uses a recursive step to consider two cases: the last element in its natural position (E(n, k-1)) and the last element not in its natural position (E(n-1, n-k). The function calls itself and continues until reaching the base cases. The main function serves as a driver program to test the function with specific values.
FileName:EntringerNumber1.java
import java.util.*;
public class EntringerNumber1 {
// Function to calculate Entringer Number E(n, k)
static int calculateEntringerNumber(int n, int k) {
// Base Case: E(0, 0) = 1
if (n == 0 && k == 0)
return 1;
// Base Case: E(n, 0) = 0 for n > 0
if (k == 0)
return 0;
// Recursive step: E(n, k) = E(n, k-1) + E(n-1, n-k)
return calculateEntringerNumber(n, k - 1) +
calculateEntringerNumber(n - 1, n - k);
}
/* Driver program to test the Entringer Number function */
public static void main(String[] args) {
int n = 4, k = 2;
int result = calculateEntringerNumber(n, k);
System.out.println( result);
}
}
Output:
4
Complexity analysis: The code calculates Entringer numbers using a recursive algorithm, resulting in an exponential time complexity of O(2^n) due to the recursive nature of the algorithm. The space complexity is determined by the depth of the recursion stack, with the worst-case height reaching O(n). Memoization or dynamic programming can optimize the solution, reducing redundant calculations and bringing the time complexity closer to O(n^2).