Parth Patel Parth Patel - 1 month ago 7
C++ Question

computes the number of ways to partition n into the sum of positive integers c++

I need to write function as part of assignment..
I need to compute the number of ways to partition n into the sum of positive integers and I can't use for while or goto

/*
* REQUIRES: n > 0
* EFFECTS: computes the number of ways to partition n into the sum of
* positive integers
* MUST be tree recursive
* Hint: Use a helper function that computes the number of ways to
* partition n using a bounded subset of integers. Then use logic
* similar to count_change() from lecture to divide partitions into
* those that use a specific item and those that do not.
*/
int num_partitions(int n);


I figured a way to print them but unable to count it and my function also needed for loop. Here's function

void print(int n, int * a) {
int i ;
for (i = 0; i <= n; i++) {
printf("%d", a[i]);
}
printf("\n");
}

int integerPartition(int n, int * a, int level,int c){
int first;
int i;
if (n < 1)
{
return c;
}
a[level] = n;
print(level, a);
c++;
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n / 2; i++){
a[level] = i;
integerPartition(n - i, a, level + 1,c);
}
}
int num_partitions(int n){
int * a = (int * ) malloc(sizeof(int) * n);
return integerPartition (n, a, 0,0);

}


please help...

here is the count change function

int count_change(int amount, const int coins[], int num_coins) {

if (amount == 0) {

return 1;

} else if​ (amount < 0 || num_coins < 1) {

return 0;

} else {

return
count_change(amount - coins[num_coins - 1], coins, num_coins) +

count_change(amount, coins, num_coins - 1);
}

}

Answer

You can do it like this:

#include <conio.h>
#include <iostream>

using namespace std;
int integerPartition(int n, int k);

int main() 
{ 
    int n;
    cin>>n;
    int k =n;
    cout<<integerPartition(n,k);

    getchar();
    return 0;                                                   
}        
int integerPartition(int n, int k)
{
    if(k==0)
        return 0;
    if(n ==0)
        return 1;
    if(n<0)
        return 0;

    return integerPartition(n,k-1) + integerPartition(n-k,k);
}

Inspired from: http://www.programminglogic.com/integer-partition-algorithm/

or you can also use: recurrence formula for partition functions, given on
https://en.wikipedia.org/wiki/Partition_(number_theory)

Comments