Partition generator and counter

I have started to study C++. After having read most of Stroustrup's book and part of 'Thinking in C++', volumes 1 and 2, I decided to do some not-so-boring exercises. The first one I posed myself was this: a program to compute all the partitions of a given size k of an integer number N. That is, all the different ways of expressing N as a sum of k terms (without regard to order). To wit, for N=10 and k=4, there are 9 partitions:

7 1 1 1
6 2 1 1
5 3 1 1
5 2 2 1
4 4 1 1
4 3 2 1
4 2 2 2
3 3 3 1
3 3 2 2

The source code is available here. The tar file contains a Makefile, a README and the partitions.cpp, partitions.h files. I think this exercise is worth being kept on line.

The main tools are the vector class, with a normal iterator and a reverse_iterator, recursion (as a mathematician, I tend to think recursively more than not) and recursion elimination (as a mathematician, I like solving problems well). The recursive version may segfault for large sizes, as

$ ./partitions 100000 100000

for example, and is unreliable also for large sizes (may output 0, for example).

To use it, download the source, untar it and make it. Then simply run

$ ./partitions N k

where N and k are positive integer numbers.

The program accepts the following command-line options:

-p: output the list of partitions to stdout
-n: run in non-recursive mode (the speed difference is noticeable for N ~ 250, s ~ 6).

The final result (the total number of partitions) is sent to stderr, which you may find useful:

$ ./partitions -p 100 20 >file

saves all the partitions in 'file' and outputs the total number. Back to Pedro's page