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:

5
4+1
3+1+1
2+1+1+1
1+1+1+1+1
2+2+1
2+3

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

Description:    
    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]); 
    }
    printf("\n"); 
}
/*
=====================
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); 
return(0);
}
Advertisements

~ 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:

WordPress.com Logo

You are commenting using your WordPress.com 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: