สมมติว่ามีจำนวนเต็มสองจำนวน 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 ตัวสุดท้ายไว้ที่เดิม ส่วนองค์ประกอบที่เหลือจะย้าย ซึ่งองค์ประกอบที่ i จะถูกวางที่ตำแหน่ง (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
