Entringer Number In C++

In this guide, we will explore the Entringer Number concept in C++ along with its practical implementation using various methods.

What is the Entringer Number?

An Entringer number is denoted as E(n, k), where n represents the total count of elements increased by one, and k signifies the required count of ascents within the elements. This numerical value helps determine the total permutations possible with elements arranged in ascending and descending order, ensuring that the specified number of ascents (k) is included in the permutation.

For Example:

If the Entringer number is E(4, 2), the count of possible permutations is:

3 2 4 1 5

3 2 5 1 4

3 1 4 2 5

3 1 5 2 4

Therefore, the total permutations possible are 4

The applications of the Entringer number are:

These numerical values are primarily utilized in combinatorial counting. Entringer numbers are computed through dynamic programming techniques and play a crucial role in algorithmic solutions. They offer insights into combinatorial patterns and configurations.

Example 1:

Let's consider a C++ code to compute the Entringer number.

#include <iostream>
using namespace std;
int entringerNumber(int length, int index) {
    if (length == 0 && index == 0){
        return 1;
    }
    if (index == 0){
        return 0;
    }
    return entringerNumber(length, index - 1) +
           entringerNumber(length - 1, length - index);
}
int main() {
    int length, index;
    cout << "Enter the length of permutations: ";
    cin >> length;
    cout << "Enter the index for Entringer Number calculation: ";
    cin >> index;
    cout << "Entringer Number E(" << length << ", " << index << "): " << entringerNumber(length, index) << endl;
    return 0;
}

Output:

Explanation:

The program includes two variables: "length," denoting the permutation's length, and "index," indicating the value of k in the Entringer number representation. User input is required to assign values to these variables. The function "entringerNumber" is utilized to recursively compute the Entringer number.

The recursive function accepts two parameters: a number and an index. If the length equals zero and the index is zero, it is common knowledge that only one potential entringer number exists, thus it yields 1. In cases where the index is zero but the length is not, the function will return zero. Otherwise, the function will make two recursive calls: one reducing the length by 1, and the other reducing both the length and index by 1. The main function invokes this entringerNumber function initially.

Example 2: Using Dynamic Programming

Let's explore a different C++ code example that utilizes dynamic programming to compute the Entringer number.

#include <iostream>
#include <vector>
using namespace std;
int entringerNumberDP(int length, int index) {
    vector<vector<int>> dp(length + 1, vector<int>(index + 1, 0));
    for (int i = 0; i <= length; ++i){
        dp[i][0] = 0;
    }
    for (int j = 0; j <= index; ++j){
        dp[0][j] = 1;
    }
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= index; ++j) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][i - j];
        }
    }
    return dp[length][index];
}
int main() {
    int length, index;
    cout << "Enter the length of permutations: ";
    cin >> length;
    cout << "Enter the index for Entringer Number calculation: ";
    cin >> index;
    cout << "Entringer Number E(" << length << ", " << index << "): " << entringerNumberDP(length, index) << endl;
    return 0;
}

Output:

Explanation:

This software computes the Entringer number based on the provided length and index, offering an optimized solution compared to the previous recursive method. By employing dynamic programming techniques, the runtime is significantly reduced. To execute this program, the user inputs the desired length and index values. A 2D vector of dimensions (length+1) by (index+1) is initialized. Subsequently, a series of nested loops is utilized to traverse the cells within the dynamic programming table, iterating from position (1,1) to (length, index). Within this process, the formula E(i,j) = E(i,j-1) + E(i-1,j-1) is applied to determine the Entringer number at each cell. The results are then stored in the DP table for future reference and can be leveraged in subsequent iterations.

Example 3: Using dynamic programming and optimising the space

Let's consider a C++ implementation for computing the Entringer number utilizing dynamic programming while optimizing memory usage.

#include <iostream>
#include <vector>
using namespace std;
int entringerNumber(int length, int index) {
    vector<int> entringerDP(index + 1, 0);
    entringerDP[0] = 1;
    for (int len = 1; len <= length; len++) {
        vector<int> current(len + 1, 0);
        for (int idx = 1; idx <= len; idx++) {
            current[idx] = current[idx - 1] + entringerDP[len - idx];
        }
        entringerDP = current;
    }
    return entringerDP[index];
}
int main() {
    int length, index;
    cout << "Enter the length of permutations: ";
    cin >> length;
    cout << "Enter the index for Entringer Number calculation: ";
    cin >> index;
    cout << "Entringer Number E(" << length << ", " << index << "): " << entringerNumber(length, index) << endl;
    return 0;
}

Output:

Explanation:

This code represents an improvement in space efficiency compared to the previous version. Instead of utilizing a 2D array for dynamic programming as in the prior version, this implementation employs a single array for the same purpose. Consequently, the space complexity of this program is reduced to O(n), while maintaining a time complexity of O(n*k).