Integer partition: code works - any suggestion to improve it?

[mrboolf]

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 actuallyhow 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_PARTITION

partition.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 :)

[StuXYZ]

First of all thanks for posting something that isn't a homework question :) [or at least doesn't read like one].

Secondly, I assume that you are writing this to do something. So I am guessing to how you want to use them.

Next: I have used partitions in real code, but I never store them, I use them as iterators. I want a begin() and end(), so that I can do the correct path integral in a loop. Yes your code can do that but it is a bit of a drag to store all that memory. Having said that it isn't a big problem

The most important thing is to sort the list. In a normal QM path integral 1+1+1+1 is normally much bigger than 4. So it is possible to calculate the first few in the set and ignore the remaining ones. The ordering is normally problem specific.

Algorithmically, you can do you construction loop by recursion, or just by counting up. It is easier (I think). That way the previous solutions on the vector can all be used, and just copied in.

Finally, return const references from both getPartition and getPartitions..

Overall thanks for the post.

[mrboolf]

Thank you for the interesting reply.

I fear that you assumed a little too much about my actual skills - I'm just at the beginning of my 2nd year of a math degree and I know nothing about QM at the moment. I'll bear this thread in mind for a more productive time to come :-)

I just wanted to generate partitions for the integers { 1 to 50 } ( I got curious after a couple of algebra exercises and I wanted to make it in c++). Hope this won't disappoint you :P

I appreciate your suggestions (I changed return from getPartition(s) ) and I thank you for your time!

One last (OT) thing: I mistakenly clicked upon "flag bad post" link (no intention to do it at all) - I immediately closed the window and I hope that didn't caused any trouble. In case it did, please ignore the report and accept my apologies.

[VernonDozier]

A few things. One, as StuXYZ mentions, an interesting and refreshing problem. Two, there are definitely several ways to do this. As the link you cite mentions, after a while, the numbers of partitions and the length of the partitions themselves get pretty big, so you have both efficiency and memory constraints. You're going up to 50 so it may not be an issue. This is definitely a paper and pencil exercise till you see a pattern:

1  {1}
2  {1,1}, {2}
3  {1,1,1}, {1,2}, {3}
4  {1,1,1,1}, {1,1,2},  {1,3}, {2,2}, {4}
5  {1,1,1,1,1},{1,1,1,2},{1,1,3},{1,2,2},{1,4},{2,3}, {5}

The ones in black are directly generated from the row immediately above, sticking a 1 in front. The ones in green are generated from TWO rows above by sticking a 2 in front of any partition in that row that does NOT have a 1. The red partition is the number itself. In the sixth row, when you calculate it, check THREE rows above and add a 3 to the front of any partition that doesn't have a 1 or 2. I only have three colors to work with (black, green, red), so I'll have to be creative:

Row 6 (generated from row 5)
{1,1,1,1,1,1},{1,1,1,1,2},{1,1,1,3},{1,1,2,2},{1,1,4},{1,2,3},{1,5}

Row 6 (generated from row 4)
{2,2,2}, {2,4}

Row 6 (generated from row 3)
{3,3}

Row 6 (new trivial partition)
{6}

I don't see your program taking advantage of the earlier partitions that you have created. This particular implementation would be more suited to linked lists than vectors. You are always simply adding an element to the front. Perhaps a vector of linked lists? A vector of vectors would work too, as you have it, but would use more memory and involve a lot of deep copying. My points above involve the mathematical generation of the partitions more so than the programming implementation.

[mrboolf]

Storing all the partitions is definitely a problem - as you can see from the Wikipedia page the value of p(n) increases really fast...

* p(1) = 1
    * p(2) = 2
    * p(3) = 3
    * p(4) = 5
    * p(5) = 7
    * p(6) = 11
    * p(7) = 15
    * p(8) = 22
    * p(9) = 30
    * p(10) = 42
    * p(100) = 190,569,292
    * p(1000) = 24,061,467,864,032,622,473,692,149,727,991 ≈ 2.4 × 10^31

For what was my need my program worked fine but I think that for greater number writing to a file each partition would be more practical than storing all of them in a vector of vectors or a vector of linked lists. (not in terms of time but in terms of memory - current program doesn't even succeed in calculating partitions of 100)

You take advantage of several previous partitions in order to generate the next one and you generate them in lexicographic order (from { 1, ..., 1 } to { N } ) while I only use the previous one.
I did it in the opposite order because I found this easier to think but undoubtely it's going to be interesting trying to implement an algorithm like the one you pointed out (I'm going to try it soon - I'll post it here when I'm done).

Just a short example of how my idea works: let's say N = 4.

The first, trivial partition is going to be{ 4 }
Then we take the rightmost element >= 1 (in this first iteration it could only be 4) and we decrease it by 1, immediately placing a 1 at its right to mantain the sum = 4.
We have now the partition { 3, 1 } and since there is only one trailing 1 we leave it as it is.
At the second loop iteration, we decrease 3 by one and insert 1 at it's right, obtaining { 2, 1, 1 }. This time the trailing 1 are enought to be grouped and we do it with the inner while loop, hence obtaining the partition { 2, 2 }.
This time, at loop iteration #3, the rightmost non-1 element is the second 2, so we repeat the procedure with it obtaining partition { 2, 1, 1 }. Only the last 1 is considered to be trailing so no grouping is done.
With loop iteration #4 we only have to split the first 2 to obtain partition { 1, 1, 1, 1 } . No grouping it's done because every sum would exceed the value of 1 (the last element changed). With this partition we are done.

Do you think that going in lexicographic order would be less expensive? I don't have immediate ideas at the moment to invert the procedure - I'll give it more thinking :-)

Thank you too for replying!

[VernonDozier]

In terms of both efficiency and memory, but especially efficiency, if you decide to go the vector route, consider sizing the vector ahead of time rather than using push_back. If you know ahead of time that you are going to have 190,569,292 elements in the vector, that is an awful lot of vector resizing that is going to go on that is avoidable if you specify the size originally. That saves you all of the deep copy time with the resizing and it saves you a lot of space that the vector is allocating in its "best guess" of what you need. What if you need 1001 spaces, the vector allocates 1000, you push_back 1000 times, then push_back another element? The vector may decide to double its size, so it does a full deep copy of 1000 elements, allocates 2000 elements for its new size, and thus 999 elements are now empty, never to be used. Specify 1001 up front, or at least a good guess, and you save deep copy time and space wasted by an inaccurate vector size by the program because it has no way of knowing.

If you do a linked list implementation and only add one element at a time to a previous partition to make a successive partition, you can save both copy time and space. Take a partition of 6:

class node
{
    int value;
    node* next;

    // constructor
    node (int val, node* nxt);
}

class partition
{
    int partitionSum;  //  number being partitioned
    node* head;

    // constructor
    partition (int partsum, node* hd);
}

Suppose you have a partition of 6: {1,1,1,1,1,1}. To turn it into a partition of 7, add a single node with value 1 in the front.:

partition sixpart; // some partition of 6
// fill sixpart with {1,1,1,1,1,1} partition
node* newnode = new node (1, sixpart->head);
partition sevenpart = new partition (7, newnode);

You have a new partition of 7 using the old partition of 6 and only adding one node in front. More efficient both space-wise and time-wise than deep copying all six integers, particularly when it becomes 60 integers instead of 6.

Whether you order it large to small or small to large probably doesn't matter, depending on how you do it. The key point is consistency and to do it in a methodical manner so you can avoid repeats, avoid omissions, and know when you are "done" without having to make an exhaustive search. Insert things correctly and in order and you won't have to traverse the whole vector or linked list. Lots of ways to do it.

[StuXYZ]

Given the HUGE size increase, if you have a calculation that can be done out to a large number, then the iterator route is best, (calculating the next on the fly). However, I haven't needed that by n=4 the quantum mech path calculation is (a) decaying to nothing (b) getting very inaccurate [numerically] (c) getting to take a very very long time.

[mrboolf]

Sorry for replying so late guys but I was kinda busy.

Anyway, thanks VernonDozier for the interesting explanation of vector's push_back behaviour - now I can see the advantages of a linked list approach. I think I'll give it a try.

@ StuXYZ: Your talking about iterators matched my curiosity so I experimented a little. I found it a little nasty since I never provided any of my classes with iterator support and I had trouble finding useful examples on the web. Here's what I came up with at last, please be easy with judgement because I never tried this kind of thing and there's the possibility I misunderstood pretty much of it :P

Following the code there are the symptomes of something that still needs to be fixed - I think it's not a big deal (at least I hope so) but I would appreciate much any clarification.

partition.h

#include <vector>

#ifndef H_PARTITION
#define H_PARTITION

void printPartition(std::vector<int>& part);

class Partition {
	private:
		std::vector<int> currPart;
		int Number;
	public:
		class Iterator {
			friend class Partition;
			Partition* partition;
			public:
				Iterator(void) { partition = NULL; }
				Iterator(const Iterator& i) { partition = i.partition; }
				Iterator(Partition& p) { partition = &p; }
				std::vector<int>& operator*(void) { return (std::vector<int>&) partition->currPart; }
				Iterator operator++(void);
				bool operator==(Iterator op2) 
					{ if(partition) { 
						return (partition->currPart==op2.partition->currPart) ?
						true : false; }
					else {
						return (op2.partition) ? false : true; } }
				bool operator!=(Iterator op2) { return !(*this==op2); }
		};
		friend class Iterator;
		Partition(int num) { Number = num; currPart.push_back(Number); }
		Iterator begin(void) { return Iterator(*this); }
		Iterator end(void) { return Iterator(); }
};

#endif // H_PARTITION

partition.cpp

#include "partition.h"
#include <iostream>

Partition::Iterator Partition::Iterator::operator++(void) {
	if(partition->currPart[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 < partition->currPart.size(); i++) { 
			// finds the rightmost element != 1
			if(partition->currPart[i]>1) {
				k++;
			}
		}
		partition->currPart[k]--; // decreases the rightmost element != 1
		partition->currPart.insert(partition->currPart.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 < partition->currPart.size(); i++) { 
				// groups trailing 1s preserving 
				// monotonicity of the sequence
				if(grouped+partition->currPart[i]
					<= partition->currPart[k]) {
					grouped += partition->currPart[i];
					partition->currPart.erase(partition->currPart.begin()+i); 
					// deletes 1s as they're added
					i--;
				}
			}
			if(grouped!=0) { // inserts the grouped 1s (if any)
				partition->currPart.insert(partition->currPart.begin()+k+1, grouped);
			}
			int sum = 0;
			for(unsigned int j = 0; j  < partition->currPart.size(); j++) {
				if(partition->currPart[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 {
		*this = Iterator(partition->end());
	}
	return *this;
}

void printPartition(std::vector<int>& part) {
	for(unsigned int i = 0; i < part.size() - 1; i++) {
		std::cout << part[i] << " + ";
	}
	std::cout << part[part.size()-1] << std::endl;
}

test1.cpp

#include "partition.h"
#include <iostream>

int main(void) {
	Partition number(4);
	Partition::Iterator i = number.begin();
	printPartition(*i);
	++i;
	printPartition(*i);
	++i;
	printPartition(*i);

	++i;
	printPartition(*i);
	++i;
	printPartition(*i);
	return 0;
}

test2.cpp

#include "partition.h"
#include <iostream>

int main(void) {
	Partition number(4);
	for(Partition::Iterator i = number.begin(); i != number.end(); ++i) {
		printPartition(*i);
	}
	return 0;
}

Well, test1 works fine while test2 doesn't. It gives segmentation fault, I think the problem is within the operator!= but it still eludes me no matter how much I look at the screen.

I hope my first attempt with iterators does actually make sense but in case it doesn't please point it out :-S I'm still a bit confused...

Thanks for your time if you read all this.

[VernonDozier]

If this is your FIRST attempt at iterators, don't do this, in my opinion. Go through tutorials first, don't try to write an iterator class, use friends, make access private, etc. Myself, I've never been very good with iterators. I started to debug your code and I think I see the problem with it, but I'm not too great at debugging with Visual C++, at least not while using iterators, so I couldn't really confirm. I find the ternary operator extremely frustrating to debug and I started to do so with your code, but stopped. I think you need to replace a lot of your ternary and compound code statements with simple statements so you can put breakpoints and debugging statements and see EXACTLY how far you get before it crashes. You can't do that just by looking at the code if this is new to you, and you can't really put a breakpoint in the middle of a compound statement to see EXACTLY how far it gets before crashing, which is what you need to be doing here. This is all the more true if you are a beginner with iterators (or anything else). Keep it simple.

On another note, I have attached my implementation using a linked list below. You said you wanted to try your own implementation, so I attached rather than posted in case you didn't want to see it yet before doing your own. It's working well. It was generating all of the partitions of the numbers 1 through 60 in a second on my machine. It ran out of memory at about 85. I'll post it in a few days too, but for now I just attached it.

[mrboolf]

Thank you for just attached it.
I count to dedicate to the list implementation tomorrow - now I'm too tired (1 am here :P).

You're probably right suggesting me to slow down with iterators - I've just used them for dummy tasks with vectors so far. I didn't find much about how actually implement iterator support, so I proceeded almost blindly (taking inspiration from a couple of java examples here and there) trying to replicate the behaviour of the few times I've used std::vector's iterators.
Anyway I fixed what was wrong with it. A silly mistake but I didn't noticed it before...
It was in the operator==, here's the (working) new partition.h file:
partition.h

#include <vector>

#ifndef H_PARTITION
#define H_PARTITION

void printPartition(std::vector<int>& part);

class Partition {
	private:
		std::vector<int> currPart;
		int Number;
	public:
		class Iterator {
			friend class Partition;
			Partition* partition;
			public:
				Iterator(void) { partition = NULL; }
				Iterator(const Iterator& i) { partition = i.partition; }
				Iterator(Partition& p) { partition = &p; }
				std::vector<int>& operator*(void) { return (std::vector<int>&) partition->currPart; }
				Iterator operator++(void);
				bool operator==(Iterator op2) 
					{ if(partition&&op2.partition) { 
						return (partition->currPart==op2.partition->currPart) ?
						true : false; }
					else {
						return (partition==op2.partition) ? true : false; } }
				bool operator!=(Iterator op2) { return !(*this==op2); }
		};
		friend class Iterator;
		Partition(int num) { Number = num; currPart.push_back(Number); }
		Iterator begin(void) { return Iterator(*this); }
		Iterator end(void) { return Iterator(); }
};

#endif // H_PARTITION

It works fine up to N = 65 (it takes ~ 20 seconds).
I tried it with N = 100 and it completed after 51m42.426s (!!)

It's a very long time but at least memory isn't an issue anymore...

Should someone had well made tutorials on iterators to point out I'll be much grateful :)
Also criticisim to that first encounter of the third kind with iterators is really welcomed!

Thanks to all participants to this thread - it's teaching me a lot.

[mrboolf]

Ok sorry for the delay.

I couldn't come up with a decent thought on how to effectively use the structure of linked lists to my advantage - I basically rewrote my first shot using a list of vectors instead of a vector of vectors :-( .
Apart from writing a linked list template class I almost never used linked lists so I guess that my brain is a little lazy playing with them.

Good thing is that I watched VernonDozier implementation and... wow.
I liked it. Took me a while to appreciate it but I liked it. I'm still studying it. I have to say that I'm learning more from this thread (and from this forum in general) than from a whole c++ class at the university.

Thank you very much guys :-)