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:
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 100000for 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 kwhere N and k are positive integer numbers.
The program accepts the following command-line options:
The final result (the total number of partitions) is sent to stderr, which you may find useful:
$ ./partitions -p 100 20 >filesaves all the partitions in 'file' and outputs the total number.