# 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