C++ প্রোগ্রাম: নির্দিষ্ট কেসের জন্য ইন্টিজার পার্টিশন করা

এটি একটি নির্দিষ্ট কেসের জন্য ইন্টিজার পার্টিশন করার C++ প্রোগ্রাম। এই প্রোগ্রামে, একটি পজিটিভ ইন্টিজার n দেওয়া থাকে, এবং n-কে পজিটিভ ইন্টিজারগুলোর যোগফল হিসেবে রিপ্রেজেন্ট করার সব সম্ভাব্য ইউনিক উপায় জেনারেট করতে হবে।

অ্যালগরিদম

শুরু
  ফাংশন displayAllUniqueParts(int m):
    1) একটি পার্টিশনে লাস্ট এলিমেন্টের ইনডেক্স k = 0 সেট করুন
    2) প্রথম পার্টিশনটি নিজেই সংখ্যাটি হিসেবে ইনিশিয়ালাইজ করুন, p[k] = m
    3) একটি হোল লুপ তৈরি করুন যা প্রথমে কারেন্ট পার্টিশন প্রিন্ট করবে, তারপর পরবর্তী পার্টিশন জেনারেট করবে। লুপটি থামবে
       যখন কারেন্ট পার্টিশনে সব ১ থাকবে।
    4) কারেন্ট পার্টিশন ডিসপ্লে করুন displayArray(p, k + 1) দিয়ে
    5) পরবর্তী পার্টিশন জেনারেট করুন:
    6) val = 0 ইনিশিয়ালাইজ করুন।
       p[]-এ ডানদিকের নন-ওয়ান ভ্যালু খুঁজুন। একসাথে val আপডেট করুন যাতে আমরা জানতে পারি কতটুকু ভ্যালু একোমোডেট করা যাবে।
       যদি k < 0,
         সব ভ্যালু ১ তাই আর কোনো পার্টিশন নেই
         উপরে পাওয়া p[k] ডিক্রিমেন্ট করুন এবং val অ্যাডজাস্ট করুন।
    7) যদি val বেশি হয়,
       তবে সর্টেড অর্ডার লঙ্ঘিত হয়। val কে p[k] সাইজের ভিন্ন ভিন্ন ভ্যালুতে ভাগ করুন এবং এই ভ্যালুগুলো p[k]-এর পরে বিভিন্ন পজিশনে কপি করুন।
       val কে পরবর্তী পজিশনে কপি করুন এবং পজিশন ইনক্রিমেন্ট করুন।
শেষ

উদাহরণ

#include <iostream>
using namespace std;

void displayArray(int p[], int m) { // অ্যারে প্রিন্ট করার জন্য
    for (int i = 0; i < m; i++)
        cout << p[i] << " ";
    cout << endl;
}

void displayAllUniqueParts(int m) {
    int p[m];
    int k = 0;
    p[k] = m;
    while (true) {
        displayArray(p, k + 1);
        int val = 0; // val ইনিশিয়ালাইজ
        while (k >= 0 && p[k] == 1) {
            val += p[k]; // val আপডেট
            k--;
        }
        if (k < 0)
            return;
        p[k]--;
        val++;
        // যদি val বেশি হয়
        while (val > p[k]) {
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}

int main() {
    cout << "Display All Unique Partitions of integer:7\n";
    displayAllUniqueParts(7);
    return 0;
}

আউটপুট

Display All Unique Partitions of integer:7 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1