দুটি সংখ্যা e এবং p দেওয়া আছে। লক্ষ্য হলো e টি এলিমেন্টवाले একটি সেটকে p টি পার্টিশন/সাবসেটে ভাগ করার পদ্ধতির সংখ্যা বের করা।
উদাহরণ ১
ইনপুট
e=4 p=2
আউটপুট
একটি সেটকে k সাবসেটে ভাগ করার পদ্ধতির সংখ্যা: 7
ব্যাখ্যা
যদি এলিমেন্টগুলো হয়: a b c d তবে ২টি পার্টিশনে ভাগ করার পদ্ধতিগুলো: (a,b,c)-(d), (a,b)-(c,d), (a,b,c)-(d), (a)-(b,c,d), (a,c)-(b,d), (a,c,d)-(b), (a,b,d)-(c)। মোট ৭টি পদ্ধতি।
উদাহরণ ২
ইনপুট
e=2 p=2
আউটপুট
একটি সেটকে k সাবসেটে ভাগ করার পদ্ধতির সংখ্যা: 1
ব্যাখ্যা
যদি এলিমেন্টগুলো হয়: a b তবে ২টি পার্টিশনে ভাগ করার পদ্ধতি: (a)-(b)। মাত্র ১টি পদ্ধতি।
প্রয়োগ করা পদ্ধতি
এই পদ্ধতিতে ডাইনামিক প্রোগ্রামিং ব্যবহার করা হয়। সমাধানে ব্যবহৃত গণনাগুলো রিকার্সিভ হয়। যদি e-1 টি এলিমেন্ট p টি পার্টিশনে ways(e-1,p) পদ্ধতিতে ভাগ করা যায়, তবে বর্তমান এলিমেন্টটি সেসব p টি পার্টিশনের যেকোনো একটিয় রাখলে p*ways(e-1,p) পদ্ধতি হবে।
যদি e-1 টি এলিমেন্ট p-1 টি পার্টিশনে ways(e-1,p-1) পদ্ধতিতে ভাগ করা যায়, তবে ১টি এলিমেন্ট আলাদা ১টি পার্টিশনে রাখলে 1*ways(e-1,p-1) পদ্ধতি হবে। মোট পদ্ধতি = p*ways(e-1,p) + ways(e-1,p-1)। এই পদ্ধতিটি রিকার্সিভ হয়ে যাবে।
উপরের চিত্রে দেখা যাচ্ছে ডুপ্লিকেট গণনা হচ্ছে। এটা এড়াতে ডাইনামিক প্রোগ্রামিং ব্যবহার করা হয়।
ভেরিয়েবল
elementsএবংpartitionইনপুট নিন।partition_k(int elements, int partition)ফাংশনটি পদ্ধতির সংখ্যা রিটার্ন করে।২D অ্যারে
arr[elements + 1][partition + 1]নিনways(e,p)এর মানarr[e][p]-এ রাখার জন্য।forলুপ দিয়েi=0থেকেi=elementsপর্যন্তarr[i][0] = 0সেট করুন কারণ পার্টিশন ০ হলে পদ্ধতি ০।আরেক
forলুপ দিয়েj=0থেকেj=partitionপর্যন্তarr[0][j] = 0সেট করুন কারণ এলিমেন্ট ০ হলে পদ্ধতি ০।এখন দুটি নেস্টেড
forলুপ দিয়েi=1থেকেi<=elementsএবংj=1থেকেj<=iপর্যন্ত বাকি মানগুলো পূরণ করুন।একক এলিমেন্টের জন্য পদ্ধতি ১, অথবা
xএলিমেন্টকেxপার্টিশনে ভাগ করলে মাত্র ১ পদ্ধতি। তাইi==jঅথবাj==1হলেarr[i][j] = 1সেট করুন।অন্যথায়
temp_1 = arr[i-1][j-1]এবংtemp_2 = arr[i-1][j]নিয়েarr[i][j] = j * temp_2 + temp_1আপডেট করুন।সকল লুপ শেষে
arr[elements][partition]-এ মোট পদ্ধতি থাকবে।arr[elements][partition]রিটার্ন করুন ফলাফল হিসেবে।
উদাহরণ কোড
#include<iostream>
using namespace std;
int partition_k(int elements, int partition) {
int arr[elements + 1][partition + 1];
for(int i = 0; i <= elements; i++) {
arr[i][0] = 0;
}
for(int j = 0; j <= partition; j++) {
arr[0][j] = 0;
}
for(int i = 1; i <= elements; i++) {
for (int j = 1; j <= i; j++) {
if (j == 1 || i == j) {
arr[i][j] = 1;
} else {
int temp_1 = arr[i-1][j-1];
int temp_2 = arr[i-1][j];
arr[i][j] = j * temp_2 + temp_1;
}
}
}
return arr[elements][partition];
}
int main() {
int elements = 4;
int partition = 2;
cout << "একটি সেটকে k সাবসেটে ভাগ করার পদ্ধতির সংখ্যা: " << partition_k(elements, partition);
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:
একটি সেটকে k সাবসেটে ভাগ করার পদ্ধতির সংখ্যা: 7
