Integer partitions

partitions.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

void partitions(int n, int max_n, vector<int>& v, vector<vector<int> >& vv)
{
    if (n == 0) {
        vv.push_back(v);
        return;
    }
    for (int i = min(n, max_n); i > 0; i--) {
        v.push_back(i);
        partitions(n - i, i, v, vv);
        v.pop_back();
    }
}

int main(int argc, char* argv[])
{
    if (argc < 2) {
        cerr << "Usage: " << argv[0] << " number [max_number_in_partitions]" << endl;
        exit(1);
    }
    int n = atoi(argv[1]);
    int max_n = argc > 2 ? atoi(argv[2]) : n;
    vector<vector<int> > vv;

    partitions(n, max_n, vector<int>(), vv);

    cout << n << " (max " << max_n << "): " << vv.size() << endl;
    for (vector<vector<int> >::const_iterator p = vv.begin(); p != vv.end(); ++p) {
        for (vector<int>::const_iterator q = p->begin(); q != p->end(); ++q)
            cout << " " << *q;
        cout << endl;
    }

    return 0;
}

partitions.py

def partitions(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    # modify partitions of n-1 to form partitions of n
    for p in partitions(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]

http://handasse.blogspot.com/2010/01/blog-post.html