সমস্ত সম্ভাব্য উপায়ে একটি পূর্ণসংখ্যার বিভাজন সম্পাদনের জন্য C++ প্রোগ্রাম

একটি প্রদত্ত পূর্ণসংখ্যার সমস্ত অনন্য পার্টিশন পাওয়ার জন্য এখানে একটি C++ প্রোগ্রাম রয়েছে যেমন একটি পার্টিশন যোগ করলে একটি পূর্ণসংখ্যা হয়। এই প্রোগ্রামে, একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া হয়, এবং ধনাত্মক পূর্ণসংখ্যার যোগফল হিসাবে n উপস্থাপন করার সমস্ত সম্ভাব্য অনন্য উপায় তৈরি করে।

অ্যালগরিদম

Begin
   function displayAllUniqueParts(int m):
   Declare an array to store a partition p[m].
   Set Index of last element k in a partition to 0
   Initialize first partition as number itself, p[k]=m
   Create a while loop which first prints current partition, then generates next partition. The loop stops when the current partition has all 1s.
   Display current partition as displayArray(p, k + 1);
   Generate next partition:
   Initialize val=0.
   Find the rightmost non-one value in p[]. Also, update the val so that we know how much value can be accommodated.
   If k < 0,
      all the values are 1 so there are no more partitions
      Decrease the p[k] found above and adjust the val.
   If val is more,
      then the sorted order is violeted. Divide val in different values of size p[k] and copy these values at different positions after p[k].
      Copy val to next position and increment position.
End

উদাহরণ কোড

#include<iostream>
using namespace std;
void printArr(int p[], int m) {
   for (int i = 0; i < m; i++)
      cout << p[i] << " ";
   cout << endl;
}
void printAllUniqueParts(int m) {
   int p[m];
   int k = 0;
   p[k] = m;
   while (true) {
      printArr(p, k + 1);
      int rem_val = 0;
      while (k >= 0 && p[k] == 1) {
         rem_val += p[k];
         k--;
      }
      if (k < 0)
         return;
         p[k]--;
         rem_val++;
      while (rem_val > p[k]) {
         p[k + 1] = p[k];
         rem_val = rem_val - p[k];
         k++;
      }
      p[k + 1] = rem_val;
      k++;
   }
}
int main() {
   cout << "All Unique Partitions of 3\n";
   printAllUniqueParts(3);
   cout << "\nAll Unique Partitions of 4\n";
   printAllUniqueParts(4);
   cout << "\nAll Unique Partitions of 5\n";
   printAllUniqueParts(5);
   return 0;
}

আউটপুট

All Unique Partitions of 3
3
2 1
1 1 1
All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1