Q:

# Count the number of elements which are greater than previous element

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.

For numbers 1 to 3, there are several permutations,

```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```

Let the range is N. Therefore, the numbers are X1, X2, X3, ..., XN.

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

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.
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:

``````#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```