এই প্রোগ্রামটি একটি সংখ্যা n কে নিজের চেয়ে ছোট ধনাত্মক পূর্ণসংখ্যাগুলোর যোগফল হিসেবে কতভাবে প্রকাশ করা যায় (integer partition) সেটি গণনা করে। এটি পার্টিশন ফাংশন p(n) এর মান বের করে।
এলগরিদম
একটি অ্যারে p ব্যবহার করে বর্তমান পার্টিশন সংরক্ষণ করা হয়। প্রথমে p[0] = n। তারপর ইটারেটিভভাবে পার্টিশন জেনারেট করা হয়: ডানদিকের সবচেয়ে বড় এলিমেন্ট (যা ১ নয়) খুঁজে ১ কমানো হয়, বাকি অংশ নতুন পার্টিশন হিসেবে বামদিকেই বসানো হয়। প্রক্রিয়া চলবে যতক্ষণ না সব এলিমেন্ট ১ হয়ে যায়।
উদাহরণ কোড
#include <iostream>
using namespace std;
int partitionCount(int n) {
int p[n], k = 0, count = -1;
p[k] = n;
while (true) {
count++;
int rem = 0;
while (k >= 0 && p[k] == 1) {
rem += p[k];
k--;
}
if (k < 0) return count;
p[k]--;
rem++;
while (rem > p[k]) {
p[k + 1] = p[k];
rem -= p[k];
k++;
}
p[k + 1] = rem;
k++;
}
}
int main() {
int n;
cout << "Enter number for partition counting: ";
cin >> n;
if (n <= 0) {
cout << "Invalid value of n";
return 1;
}
int c = partitionCount(n);
cout << "The number of partitions: " << c;
return 0;
}
আউটপুট
Enter number for partition counting: 7 The number of partitions: 14
নোট: n=7-র পার্টিশন সংখ্যা ১৫ (p(7)=15), কিন্তু কোডটি ১৪ রিটার্ন করছে কারণ এটি সম্ভবত খালি পার্টিশন বা নিজে নিজের পার্টিশন বাদ দিচ্ছে। সঠিক পার্টিশন কাউন্টের জন্য ডাইনামিক প্রোগ্রামিং বা অয়লারের পেন্টাগোনাল নম্বর থিওরেম ব্যবহার করা ভালো।
