สมมติว่าเรามีจำนวนเต็ม N และ K สองจำนวน เราต้องหาการเรียงสับเปลี่ยนของจำนวนธรรมชาติจำนวน 2N แรก เพื่อให้สมการต่อไปนี้เป็นจริง
$$\displaystyle\sum\limits_{i=1}^N\lvert A_{2i-1}-A_{2i}\rvert+\lvert \displaystyle\sum\limits_{i=1}^N A_{2i-1 }-A_{2i} \rvert=2K$$
ค่าของ K ควรน้อยกว่าหรือเท่ากับ N ตัวอย่างเช่น ถ้า N =4 และ K =1 ผลลัพธ์จะเป็น 2 1 3 4 ผลลัพธ์ของนิพจน์ที่กำหนดจะเป็น (|2 – 1| + | 3 – 4|) – (|2 – 1 + 3 – 4|) =2.
แนวคิดง่ายๆ ลองพิจารณาว่าเรามีลำดับการเรียงลำดับ เช่น 1, 2, 3, 4, 5, 6, …. หากเราสลับสองดัชนี 2i – 1 และ 2i ผลลัพธ์จะเพิ่มขึ้น 2 อย่างแน่นอน เราจำเป็นต้องทำการแลกเปลี่ยน K ดังกล่าว
ตัวอย่าง
#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);
} ผลลัพธ์
2 1 4 3 5 6 7 8
