Trong một mảng, một cặp a [i], a [j] được gọi là một nghịch đảo nếu a [i]> a [j] và i
Chúng tôi có thể áp dụng phương pháp vũ phu , đầu tiên là tìm tất cả các hoán vị của N số đầu tiên và sau đó kiểm tra tất cả các nghịch đảo xem nó có bằng K hay không. Nếu có, hãy tăng bộ đếm kết quả.
Theo cách tiếp cận này, chúng ta có N chữ số của N số tự nhiên đầu tiên. Tất cả các hoán vị của số đó được tính ở một nơi khác mà từ đó chúng ta đang tìm K hoán vị. Để tìm nó, Chúng tôi sẽ chèn số tiếp theo thứ N (lớn nhất) trong tất cả các hoán vị và tìm kiếm những số có số nghịch đảo bằng K sau khi cộng số này sẽ được tính trong kết quả của chúng tôi. Lấy các hoán vị của (N - 1) số không có (K - 3) nghịch đảo như vậy, chúng ta sẽ chuyển số mới ở chỉ số thứ 3 từ cuối cùng. Số lần nghịch đảo sẽ là K và find_permutations (N-1, K-3) sẽ là câu trả lời của chúng ta. Logic tương tự có thể được sử dụng cho các nghịch đảo khác và chúng ta sẽ đi đến đệ quy ở trên như là câu trả lời cuối cùng.
Đầu vào - N =4, K =3
Đầu ra - 6
Trong bài viết này, chúng tôi giải một bài toán để tìm Số hoán vị với K nghịch đảo từ O (n * k) phức tạp về thời gian. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích. 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.
Phương pháp tiếp cận để tìm giải pháp
Phương pháp tiếp cận hiệu quả
Đầu vào
#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;
} Đầu ra
0
Kết luận
