สมมติว่าเรามีจำนวนเต็ม N และ K สองตัว และเราต้องหาการเรียงสับเปลี่ยน P ของจำนวนธรรมชาติ N ตัวแรกที่มีองค์ประกอบ K ตรงตามเงื่อนไข GCD(P[i], i)> 1 สำหรับ 1 ทั้งหมด <=i <=N ดังนั้นเมื่อ N =3 และ K =1 ผลลัพธ์จะเป็น 2, 1, 3 และ gcd(2, 1) =1, gcd(1, 2) =1, gcd(3, 3) =3
วิธีการนั้นง่าย เราจะเก็บองค์ประกอบ k สุดท้ายไว้แทนที่ องค์ประกอบที่เหลือจะถูกย้าย เพื่อให้องค์ประกอบ ith จะถูกวางไว้ในตำแหน่งที่ (i + 1) และองค์ประกอบที่ (N - K) จะถูกเก็บไว้ใน ตำแหน่ง 1 เนื่องจาก gcd(x, x+1) =1
ตัวอย่าง
#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
int permutation[n + 1];
for (int i = 1; i <= n; i++)
permutation[i] = i;
for (int i = 1; i < n - k; i++)
permutation[i + 1] = i;
permutation[1] = n - k;
for (int i = 1; i <= n; i++)
cout << permutation[i] << " ";
}
int main() {
int n = 5, k = 2;
cout << "The permutation is: ";
findPermutation(n, k);
} ผลลัพธ์
The permutation is: 3 1 2 4 5
