Problem statement:

问题陈述：

Given a range 1 to N. Among its different permutations you have to find out those permutations where only one element is greater than its previous element and you have to count that number.

给定范围1到N。 在其不同排列中，您必须找出仅一个元素大于其先前元素的那些排列，并且您必须计算该数字。

For numbers 1 to 3, there are several permutations,

对于数字1到3，有几个排列，

1 2 3       1 2 && 2 3
1 3 2       1 3
2 1 3       1 3
2 3 1       2 3
3 1 2       1 2
3 2 1       none

Input:
T no.of Testcases.
T no. Of lines along with the N values with it.

E.g.
3
2
3
4

Constrains:
1 ≤ T ≤ 10
1≤ N ≤ 9

Output:
Print the count of the permutations 
those have only one element is greater than 
the previous one.

Example

例

T=3

Input:
N=2

Output:
1 2 
Count: 1

Input:
N=3

Output:
1 3 2 
2 1 3 
2 3 1 
3 1 2 
Count: 4

Input:
N=4

Output:
1 4 3 2 
2 1 4 3 
2 4 3 1 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 2 1 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
Count: 11

Explanation with example:

举例说明：

Let the range is N. Therefore, the numbers are X₁, X₂, X₃, ..., X_N.

设范围为N。 因此，数字为X ₁ ，X ₂ ，X ₃ ，...，X _N。

Let f(i) = select an element in the permutation.

令f(i) =选择置换中的一个元素。

To know which elements are already visited in the array we will use a Boolean array and store the permutations we will use another array.

要知道数组中已经访问了哪些元素，我们将使用布尔数组，并存储排列，我们将使用另一个数组。

To find out the permutations we will follow these following steps,

为了找出排列，我们将遵循以下步骤，

1. We traverse the whole array and pick the first non-visited element from the array.

   我们遍历整个数组，并从数组中选择第一个未访问的元素。

2. Compare the current none visited element with the last element of the second array. If the last element is less than the current element, we will increase the counter value otherwise not.

   将当前未访问的元素与第二个数组的最后一个元素进行比较。 如果最后一个元素小于当前元素，我们将增加计数器值，否则不增加。

3. After the checking, we insert the current element into the second array.

   检查之后，我们将当前元素插入第二个数组。

4. Repeat step 1 to step 3 until we traverse the whole element of the array.

   重复步骤1到步骤3，直到遍历数组的整个元素。

5. After traversing the whole array, we check the counter. If the count value equals to one then we will print the second array and consider that permutation into our count.

   遍历整个数组后，我们检查计数器。 如果计数值等于一，那么我们将打印第二个数组，并考虑将这个置换计入我们的计数中。

C++ Implementation:

C ++实现：

#include <bits/stdc++.h>
using namespace std;

void permutation(bool* visit, int* arr, int ran, int& count, int pos, vector<int> v, int g_count)
{
    if (pos >= ran) {
        if (g_count == 1) {
            count++;
            for (int i = 0; i < ran; i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < ran; i++) {
        if (!visit[i]) {
            visit[i] = true;
            if (pos != 0) {
                if (v[pos - 1] < arr[i]) {
                    g_count++;
                }
            }
            v.push_back(arr[i]);
            permutation(visit, arr, ran, count, pos + 1, v, g_count);
            v.pop_back();
            visit[i] = false;
            if (pos != 0) {
                if (v[pos - 1] < arr[i]) {
                    g_count--;
                }
            }
        }
    }
}

int main()
{
    int t;
    cout << "Test Case : ";
    cin >> t;
    while (t--) {
        int ran;
        cout << "Enter the range : ";
        cin >> ran;
        int arr[ran];
        int count = 1;
        for (int i = 0; i < ran; i++) {
            arr[i] = count;
            count++;
        }
        bool visit[ran] = { false };
        count = 0;
        int pos = 0, g_count = 0;
        vector<int> v;
        permutation(visit, arr, ran, count, pos, v, g_count);
        cout << "Count : " << count << endl;
    }
    
    return 0;
}

Output

输出量

Test Case : 3
Enter the range : 2
1 2
Count : 1
Enter the range : 3
1 3 2
2 1 3
2 3 1
3 1 2
Count : 4
Enter the range : 4
1 4 3 2
2 1 4 3
2 4 3 1
3 1 4 2
3 2 1 4
3 2 4 1
3 4 2 1
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
Count : 11

翻译自: https://www.includehelp.com/icp/count-the-number-of-elements-which-are-greater-than-previous-element.aspx