ডিরেঞ্জমেন্ট হলো N সংখ্যার পারমুটেশন যাতে কোনো সংখ্যাও তার অরিজিনাল পজিশনে থাকে না। উদাহরণ: {1,2,3} এর একটি ডিরেঞ্জমেন্ট {2,3,1}। লক্ষ্য N সংখ্যার জন্য সম্ভাব্য ডিরেঞ্জমেন্টের সংখ্যা গণনা করা।
রিকার্সিভ সমাধান:
- N=0: 1 (কনভেনশন)
- N=1: 0
- N=2: 1 (সুইপ {2,1})
- N=3: 2 ({2,3,1}, {3,1,2})
- N=4: 9
- N: (N-1) * (derangements(N-1) + derangements(N-2))
লজিক: ০ নম্বর ইন্ডেক্সের এলিমেন্ট n-1 জায়গায় যেতে পারে। যদি i-ইন্ডেক্সের এলিমেন্ট ০-তে যায় তবে স্ব্যাপ হয়, বাকি n-2 এর জন্য ক্যালকুলেশন। না হলে n-1 এলিমেন্টের জন্য n-2 চয়েস।
ইনপুট
Arr[] = { 1, 2 }
আউটপুট
No. of derangements : 1
ইনপুট
Arr[] = { 1, 2, 3 }
আউটপুট
No. of derangements : 2
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- Num = সংখ্যা কাউন্ট।
- derangements(int N) রিকার্সিভ ফাংশন।
- বেইস কেস N=0,1,2 হ্যান্ডেল।
- N>2 হলে ফর্মুলা দিয়ে রিকার্সিভ কল।
- ব্যাকট্র্যাকিং-এ কাউন্ট কম্পিউট হয়।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
if (N == 0) return 1;
if (N == 1) return 0;
if (N == 2) return 1;
return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
int Numbers = 5;
cout << "Number of Derangements :" << derangements(Numbers);
return 0;
}আউটপুট
Number of Derangements :44
