Generating Integer Partitions in C/C++ (Recursive)

One of my recent projects (enumerating integer lattice points inside of hypersphere with arbitrary radius centered at origin) required a simple algorithm for integer partition. For example, I can break 5 into different parts the following ways:


Neat, ha?

Well, when I googled for this algorithm in C/C++ on the web, I wasn’t satisfied with what I found. There were many versions of it coded in any language but C, most popular was Python. And a few of them required some kind of a special library. What a shame.

C is the piano of computer programming. So below is C code, where n is the number we’re trying to partition (e.g. 5 above) and a is a pointer to array which will hold the partition.

Author:    Monsi Terdex
Date:    04/10/13

    Integer partition in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

Routine for printing out array contents
void print(int n, int * a) {
    int i ; 
    for (i = 0; i <= n; i++) {
        printf("%d", a[i]); 
The algorithm
void integerPartition(int n, int * a, int level){
    int first; 
    int i; 
    if (n < 1) return ;    
        a[level] = n;
    print(level, a);
    first = (level == 0) ? 1 : a[level-1];
    for(i = first; i <= n / 2; i++){
        a[level] = i; 
        integerPartition(n - i, a, level + 1);
int main(int argc, char ** argv){
    int n = 10;     
    int * a = (int * ) malloc(sizeof(int) * n); 
    integerPartition (n, a, 0); 

~ by Monsi.Terdex on April 12, 2013.

3 Responses to “Generating Integer Partitions in C/C++ (Recursive)”

  1. Reblogged this on justanotherhumanoid.

  2. Hey can you please explain what you algo is doing?
    i’m having a hard time understanding the recursion..

  3. You malloc’d the array ‘a’, but never freed the memory.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: