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>…

View original post 146 more words

Advertisements
Standard

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