使用 C++ 求 K 次反转的排列数
在数组中，如果a[i]>a[j]且i<j，则一对a[i],a[j]被称为反转。我们有两个数字N和k，需要计算前N个数字有多少可能的排列以完美的K反转结束。所以这是例子-
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(largest)在所有排列中插入下一个数字，并在添加这个数字后寻找那些反转计数等于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];
//递归函数
int find_permutations (int N_numbers, int K_inversion){
if (N_numbers == 0){
return 0; //当N变为0时返回0
}
if (K_inversion == 0)
return 1; //当K变为1时返回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;
}
//主功能
int main (){
int N, K;
cin >> N; //接受用户的输入
cin >> K;
cout << find_permutations (N, K);
return 0;
}输出结果0
输入−N=4，K=3
输出-6
结论
在这篇文章中，我们解决了一个问题，从O(n*k)的时间复杂度中找到K次反转的排列数。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。希望这篇文章对您有所帮助。