ডিরেঞ্জমেন্ট হল N সংখ্যার স্থানান্তর যাতে কোনো সংখ্যা মূল অবস্থানে উপস্থিত হয় না। উদাহরণস্বরূপ { 1,2,3 } এর একটি সম্ভাব্য বিভ্রান্তি হল { 2,1,3 }। এর কোনো উপাদানই তার আসল অবস্থানে নেই। এখানে লক্ষ্য হল N সংখ্যার জন্য সম্ভাব্য বিভ্রান্তি গণনা করা।
আমরা একটি পুনরাবৃত্ত সমাধান ব্যবহার করে এটি করব। নিম্নলিখিত নম্বর জন্য. উপাদানগুলির -
- N=0, কোন বিড়ম্বনা নেই, 1 ফেরত দিন
- N=1, শুধুমাত্র একটি সংখ্যা, রিটার্ন 0
- N=2, পজিশনের শুধুমাত্র একটি অদলবদল সম্ভব, { 1,2 } → { 2,1 }, রিটার্ন 1
- N=3, 2 সম্ভাব্য স্থানান্তর যেমন, { 1,2,3 } → { 2,3,1 }, { 3,1,2 } গণনা 2
- N=4, 9 সম্ভাব্য স্থানান্তর
- ....................................
- N, (N-1)*( permutation(N-1) + permutation(N-2) )
একটি অ্যারের সমস্ত উপাদানের জন্য,
-
সূচক 0 এ উপাদানটির n-1 অবস্থান রয়েছে যা এটি নিতে পারে,
-
যদি সূচী i-এর কোনো উপাদানকে সূচক 0-এ রাখা হয়, তাহলে arr[i] এবং arr[0] অদলবদল করা হয়। এখন গণনার জন্য n-2 উপাদান আছে।
-
যদি সূচী i-এর উপাদানটি সূচক 0-এ না থাকে তবে n-1 উপাদানের জন্য n-2 পছন্দ রয়েছে।
ডায়াগ্রাম
ইনপুট
Arr[] = { 1, 2 } আউটপুট
No. of derangements : 1
ব্যাখ্যা − 1 এবং 2-এর অবস্থানগুলি হল সূচক 0 এবং 1৷ শুধুমাত্র পজিশন তারা পেতে পারে আসল পজিশন অদলবদল করে৷ { 2,1 }
ইনপুট
Arr[] = { 1, 2, 3 } আউটপুট
No. of derangements : 2
ব্যাখ্যা − 1,2 এবং 3-এর অবস্থান হল সূচক 0,1,2।
1 এবং 2 সূচকে 1 স্থাপন করা যেতে পারে, 2 সূচক 0 এবং 3 এবং 3 সূচক 0 এবং 1 এ স্থাপন করা যেতে পারে।
{ 2,3,1 } এবং { 3,1,2 } হল 2টি বিভ্রান্তি৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
পূর্ণসংখ্যা সংখ্যা বর্তমান সংখ্যার গণনা সংরক্ষণ করে।
-
রিকার্সিভ ফাংশন ডিরেঞ্জমেন্ট (int N) ইনপুট হিসাবে সংখ্যার গণনা নেয় এবং নম্বর প্রদান করে। বিভ্রান্তির।
-
N=0,1,2 এর জন্য রিটার্ন স্টেটমেন্টগুলি বেস কেসগুলি পরিচালনা করছে যার জন্য পারমিউটেশনগুলি ইতিমধ্যে 1,0 এবং 1 হিসাবে গণনা করা হয়েছে৷
-
যখন N>2 তখন derangements() কে রিকার্সিভ কল করা হয় সূত্র ব্যবহার করে,
(N-1)* ( বিভ্রান্তি (N-1) + বিভ্রান্তি (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);
} আউটপুট
Number of Derangements :44
