Hi all there.
Firstly I apologize if this is not a specific question (please do point it out if you find this unpolite).
I don't have real problems so if you're not personally interested feel free to save your time and close this thread :)
Anyway, I had to write a program to generate all partitions of a given integer.
I haven't found many relevant results for this subject so I came out with the following little class and I am posting this here for two reasons:
1 - to make this thread an (hopefully relevant) entry for anyone doing a similar search in the future
2 - to ask if anyone sees any possible improvement (if you do a pointer would be much appreciated!)
I'm strictly interested in the makePartitions function, as long as actually how dealing with them is simply a matter of "do-the-dirty-job" for me at the moment.
Here's the code:
partition.h
#include <vector>
#ifndef H_PARTITION
#define H_PARTITION
class Partition {
public:
Partition(int num);
int getNumber(void);
std::vector<std::vector<int> > getPartitions(void);
std::vector<int> getPartition(int index);
void makePartitions(void);
void showPartitions(void);
int operator()(void);
private:
int Number;
std::vector<std::vector<int> > Partitions;
};
#endif // H_PARTITIONpartition.cpp
#include <iostream>
#include "partition.h"
int Partition::operator()(void) {
return Partitions.size();
}
void Partition::showPartitions(void) {
std::cout << std::endl;
for(unsigned int i = 0; i < Partitions.size(); i++) {
for(unsigned int j = 0; j < Partitions[i].size() - 1; j++) {
std::cout << Partitions[i][j] << " + ";
}
std::cout << Partitions[i][Partitions[i].size()-1]
<< std::endl;
}
}
void Partition::makePartitions(void) {
std::vector<int> temp;
temp.push_back(Number);
// the first partition for number N is equal to { N }
while(temp[0]>0) {
Partitions.push_back(temp);
// stores the last partition computed
if(temp[0]!=1) {
// if the first element of the partition is 1
// then the partition is { 1, ... , 1 } and we're done
int k = 0;
for(unsigned int i=1; i < temp.size(); i++) {
// finds the rightmost element != 1
if(temp[i]>1) {
k++;
}
}
temp[k]--; // decreases the rightmost element != 1
temp.insert(temp.begin()+k+1, 1);
// inserts 1 at its right
bool loop_again = true;
while(loop_again) {
int grouped = 0;
for(unsigned int i=k+1; i < temp.size(); i++) {
// groups trailing 1s preserving
// monotonicity of the sequence
if(grouped+temp[i]<=temp[k]) {
grouped += temp[i];
temp.erase(temp.begin()+i);
// deletes 1s as they're added
i--;
}
}
if(grouped!=0) { // inserts the grouped 1s (if any)
temp.insert(temp.begin()+k+1, grouped);
}
int sum = 0;
for(unsigned int j = 0; j < temp.size(); j++) {
if(temp[j]==1) {
sum++;
// calculates the amount of remaining 1s
}
}
if(sum>1&&grouped!=0) {
// if there are more trailing 1s and we have just
// grouped a few it sets the flag for another loop
k++;
loop_again = true;
}
else {
loop_again = false;
// this partition is done,
// so we exit the inner while loop
}
}
}
else {
temp[0]--;
// decreases the first element
// of the partition { 1, ... , 1 } to exit the loop
}
}
}
std::vector<int> Partition::getPartition(int index) {
return Partitions[index];
}
std::vector<std::vector<int> > Partition::getPartitions(void) {
return Partitions;
}
int Partition::getNumber(void) {
return Number;
}
Partition::Partition(int num) {
if(num>=0) {
Number = num;
}
else {
Number = 1;
}
}test.cpp
#include <iostream>
#include "partition.h"
#define N 6
int main(void) {
Partition number(N);
number.makePartitions();
std::cout << std::endl << "The number " << N
<< " has the following "
<< number() << " partitions:" << std::endl << std::endl;
number.showPartitions();
return EXIT_SUCCESS;
}Thanks for your consideration :)