특정 경우에 대해 정수 파티션을 수행하는 C++ 프로그램

특정 경우에 정수 분할을 수행하는 C++ 프로그램입니다. 이 프로그램에서 양의 정수 n이 주어지며 n을 양의 정수의 합으로 나타내기 위해 가능한 모든 고유한 방법을 생성해야 합니다.

알고리즘

Begin
   function displayAllUniqueParts(int m):
   1) Set Index of last element k in a partition to 0
   2) Initialize first partition as number itself, p[k]=m
   3) Create a while loop which first prints current partition, then generates next partition. The loop stops    when the current partition has all 1s.
   4) Display current partition as displayArray(p, k + 1)
   5) Generate next partition:
   6) Initialize val = 0.
   Find the rightmost non-one value in p[]. Also, update the val so that we know how much value can be ccommodated.
   If k < 0,
      All the values are 1 so there are no more partitions
      Decrease the p[k] found above and adjust the val.
   7) If val is more,
   then the sorted order is violated. 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 displayArray(int p[], int m) { //to print the array
   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; // initialize val
      while (k >= 0 && p[k] == 1) {
         val += p[k]; // update val
         k--;
      }
      if (k < 0)
      return;
      p[k]--;
      val++;
      //if val is more
      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