Partition function in c++

Question

I need an algorithmic solution in c++ for the partition-problem

Simple explanation: Find all sums that get a number n. For example

• Input: 5
• Output:
  • 11111
  • 2111
  • 311
  • 41
  • 5
  • 221
  • 23

This problem seems so easy, but I couldn't find a solution. I'm close to make this bruteforce, because the highest input is 11. The articles about that problem are highly mathematic and I don't really get it.

Thank you all!

• High Performance Mark: A quick Google will turn up algorithms for this integer partition problem in all sorts of languages; for example: homepages.ed.ac.uk/jkellehe/partitions.php. I think that your request for 'an algorithmic solution in C++' is a little wonky. do you mean 'an algorithm' or 'an implementation of an algorithm in C++' ?
• Weedjo: yeah, of course "an algorithm". I'll take a look at your link, looks good! thank :)

Answer 1

You can try a recursive approach with a function F to find all the first level partitions of the given number X, i.e X expressed as the sum of two integers a,b < X and then call F again on a and b until they can not be partitioned any more. Here is an example in Python which could be of help to you in writing your own in C++

Answer 2

/*
E.g.
input number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3
*/
#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 N;
 cout << "input number:";
 cin >> N;
 vector<int> v(N);
 part(N, v, 0);
}

Answer 3

Simply put them in a well-defined order. Then write a function to find the first entry in that order. Then write a function to find the next entry in that order. Then the problem is trivial.

For example, in the case of 5, you have two choices for the first entry, 11111 or 5. Either of those entries are trivial to generate. Then you just need an operation to get the "next entry" from a given entry. Repeat that operation until it fails and you're done.

I suggest this order:

 11111
 1112
 113
 122
 14
 23
 5

• High Performance Mark: I suggest putting 122 in there somewhere somehow.
• Weedjo: you forgot 221 ;-) I already had an algorithm with starting point 11111. the problem is to find the operation "next entry". I tried to always subtract one 1 and add it to a number right to it. but that doesn't work for n=10 for example, because you have things like 433 etc.