สมมติว่าเรามีจำนวนเต็ม N และ K สองตัว เราต้องหาการเรียงสับเปลี่ยนของจำนวนเต็มจากช่วง [1 ถึง N] เพื่อให้จำนวนดัชนี (1 – การจัดทำดัชนีฐาน) โดยที่ gcd(P[i], i)> 1 คือ ตรง K ดังนั้นถ้า N =4 และ K =3 ผลลัพธ์จะเป็น [1, 2, 3, 4] เนื่องจาก gcd(1, 1) =1, gcd(2, 2) =2, gcd(3, 3) =3, gcd(4, 4) =4
หากสังเกตดีๆ จะพบว่า gcd(i, i+1) =1, gcd(1, i) =1 และ gcd(i, i) =i เนื่องจาก GCD ของจำนวนใดๆ และ 1 เป็น 1 เสมอ K เกือบจะเป็น N – 1 ได้ พิจารณาการเรียงสับเปลี่ยนโดยที่ P[i] =i จำนวนดัชนีที่ gcd(P[i], i)> 1 จะเป็น N – 1 หากเราสลับสององค์ประกอบต่อเนื่องกัน ยกเว้น 1 จะลดจำนวนดัชนีดังกล่าวลง 2 อย่างแน่นอน และการสลับกับ 1 จะลดจำนวนลง โดยตรง 1.
ตัวอย่าง
#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
if (k >= n || (n % 2 == 0 && k == 0)) {
cout << -1;
return;
}
int P[n + 1];
for (int i = 1; i <= n; i++)
P[i] = i;
int count = n - 1;
for (int i = 2; i < n; i+=2) {
if (count - 1 > k) {
swap(P[i], P[i + 1]);
count -= 2;
} else if (count - 1 == k) {
swap(P[1], P[i]);
count--;
} else
break;
}
for (int i = 1; i <= n; i++)
cout << P[i] << " ";
}
int main() {
int n = 5, k = 3;
cout << "Permutation is: ";
findPermutation(n, k);
} ผลลัพธ์
Permutation is: 2 1 3 4 5
