Write a code using C++ to find the number of permutations with K pairs in reverse order

In an array, if a[i] > a[j] and i

Input: N = 4, K = 1
Output: 3
Explanation: Permutation of the first N numbers in total : 1234, 1243, 1324 and 2134. With 1 inversion we have 1243, 1324 and 2134.

Input : N = 3, K = 2
Output : 3
Explanation: Permutation of the first N numbers in total : 123, 132, 213, 231, 312, and 321 with 2 inversions we have 231, 312 and 321.

Solution method

We can use the brute force method, first find all the permutations of the first N numbers, and then check whether all the reversals Is it equal to K? If so, increment the result counter.

Efficient method

In this method, we have N digits of the first N natural numbers. All permutations of this number are calculated elsewhere, from which we find K permutations. To find it we will insert the next number Nth (maximum) in all permutations and after adding that number look for numbers whose inversion count equals K should be counted in our result. Taking a permutation of (N – 1) numbers without (K – 3) inversions, we would move the new number at the third index from the last index. With K number of reversals, find_permutations(N-1, K-3) will be our answer. The same logic can be used for other inversions and we will get the above recursion as the final answer.

Input

#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int a = 0;
int arr[X][X];
// recursive function
int find_permutations (int N_numbers, int K_inversion){
    if (N_numbers == 0){
      return 0;            // return 0 when N becomes 0
    }
    if (K_inversion == 0)
        return 1;            // return 1 when K becomes 1
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion];
    int result = 0;
    for (int i = 0; i <= K_inversion; i++){

        if (i <= N_numbers - 1)
          result += find_permutations (N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}
// main function
int main (){
    int N, K;
    cin >> N;    // taking input from user
    cin >> K;
    cout << find_permutations (N, K);
    return 0;
}

Output

0

Input− N = 4, K = 3

Output− 6

Conclusion

In this article, we solve a problem to find permutations of K reversals with O(n * k) time complexity. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages ​​such as C, java, python and other languages. Hope this article is helpful to you.

The above is the detailed content of Write a code using C++ to find the number of permutations with K pairs in reverse order. For more information, please follow other related articles on the PHP Chinese website!