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 個の順列が見つかります。それを見つけるために、すべての順列に次の N 番目 (最大) の数値を挿入し、その数値を追加した後、結果でカウントされるべき反転カウントが 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 などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して、K 個のペアを逆順に持つ順列の数を見つけるコードを作成します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。