Giả sử chúng ta có hai số nguyên N và K. Chúng ta phải tìm hoán vị đầu tiên của 2N số tự nhiên sao cho thỏa mãn đẳng thức sau.
$$ \ displaystyle \ sum \ limit_ {i =1} ^ N \ lvert A_ {2i-1} -A_ {2i} \ rvert + \ lvert \ displaystyle \ sum \ limit_ {i =1} ^ N A_ {2i-1 } -A_ {2i} \ rvert =2K $$
Giá trị của K phải nhỏ hơn hoặc bằng N. Ví dụ, nếu N =4 và K =1, thì kết quả đầu ra sẽ là 2 1 3 4. Kết quả của biểu thức đã cho sẽ là (| 2 - 1 | + | 3 - 4 |) - (| 2 - 1 + 3 - 4 |) =2.
Ý tưởng rất đơn giản, hãy xem xét chúng ta có một dãy đã được sắp xếp như 1, 2, 3, 4, 5, 6,…. Nếu chúng ta hoán đổi hai chỉ số bất kỳ 2i - 1 và 2i, kết quả sẽ tăng lên chính xác là 2. Chúng ta cần thực hiện K hoán đổi như vậy.
Ví dụ
#include<iostream>
using namespace std;
void showPermutations(int n, int k) {
for (int i = 1; i <= n; i++) {
int a = 2 * i - 1;
int b = 2 * i;
if (i <= k)
cout << b << " " << a << " ";
else
cout << a << " " << b << " ";
}
}
int main() {
int n = 4, k = 2;
showPermutations(n, k);
} Đầu ra
2 1 4 3 5 6 7 8