ধরুন আমাদের দুটি পূর্ণসংখ্যা 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