C++を使用してK個の転倒を伴う順列の数を見つける

配列では、a [i]> a[j]および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.

解決策を見つけるためのアプローチ

ブルートフォースアプローチを適用できます 、これは最初に最初のN個の数のすべての順列を見つけ、次にそれがKに等しいかどうかにかかわらずすべての反転をチェックします。はいの場合、結果のカウンターをインクリメントします。

効率的なアプローチ

このアプローチでは、最初のN個の自然数のN桁があります。その数のすべての順列は、K個の順列を探している別の場所で計算されます。それを見つけるために、すべての順列に次の数Nth（最大）を挿入し、この数を加算した後、転倒数がKに等しい数を探して結果にカウントする必要があります。 （K – 3）反転を持たない（N – 1）数のそのような順列を取り、最後から3番目のインデックスで新しい数をシフトします。転倒の数はKになり、find_permutations（N-1、K-3）が答えになります。同じロジックを他の反転にも使用でき、最終的な答えとして上記の再帰に到達します。

入力

#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;
}

出力

0

入力− N =4、K =3

出力-6

結論

この記事では、問題を解決して、 O（n * k）からK個の転倒を伴う順列の数を見つけます。 時間計算量。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。