c++integer-partition

Partition of an Integer + Number of partitions


A partition of an integer n is a way of writing n as a sum of positive integers. For example, for n=7, a partition is 1+1+5.

I need a program that finds all the partitions of an integer n using r integers. For example, all the partitions of n=7 using r=3 integers are 1+1+5, 1+2+4, 1+3+3, 2+2+3.

This is what I have so far:

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
    for(int i=0;i<=level;i++)
        cout << v[i] << " ";
    cout << endl;
}

void part(int n, vector<int>& v, int level){
    int first; /* first is before last */

    if(n<1) return ;
    v[level]=n;
    print(v, level);

    first=(level==0) ? 1 : v[level-1];

    for(int i=first;i<=n/2;i++){
        v[level]=i; /* replace last */
        part(n-i, v, level+1);
    }
}

int main(){
    int num;
    cout << "Enter a number:";
    cin >> num;

    vector<int> v(num);

    part(num, v, 0);
}

The output of this program is:

Enter a number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3

Process returned 0 (0x0)   execution time : 1.837 s
Press any key to continue.

How can I change my code so I can have that r variable?

EDIT:

In case it was not clear, the r value represents the number of integers per partition. So in the case above, if r=2, then the partitions can only have two integers in them. The partitions would be 4+1 and 3+2. The r value should be entered by the user.


Solution

  • Essentially what Codor said, plus you don't need to recurse further into part() once you found a partition of the target length since they would be longer:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void print (vector<int>& v, int level){
        for(int i=0;i<=level;i++)
            cout << v[i] << " ";
        cout << endl;
    }
    
    void part(int n, vector<int>& v, int level, int r){
        int first; /* first is before last */
    
        if(n<1) return ;
        v[level]=n;
        if( level+1 == r ) {
            print(v, level);
            return;
        }
    
        first=(level==0) ? 1 : v[level-1];
    
        for(int i=first;i<=n/2;i++){
            v[level]=i; /* replace last */
            part(n-i, v, level+1, r);
        }
    }
    
    int main(){
        int num,r;
        cout << "Enter a number:";
        cin >> num;
        cout << "Enter size (r):";
        cin >> r;
    
        vector<int> v(num);
    
        part(num, v, 0, r);
    }
    

    Output:

    Enter a number:5
    Enter size (r):2
    1 4
    2 3