使用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) 個數字的排列，我們將在最後一個索引的第三個索引處移動新數字。反轉次數為 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中文網其他相關文章！