This article is intended to give introduction to **integer partitioning problem**, with numerous reading material, code and explanation aggregated from various Internet sources.

In number theory, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n). – Wikipedia

Partition of number 4:

1. 4

2. 3 + 1

3. 2 + 2

4. 2 + 1 + 1

5. 1 + 1 + 1 + 1

A generating function for p(n) is given by the reciprocal of Euler’s function:

Expanding each term on the right-hand side as a geometric series, we can rewrite it as (1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The number of partitions p(n) is the coefficient of x^n in the expansion of

(1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The objective of this article is to look into the implementation of generating this ferrer’s diagram

Some more Additional Reading:

1 . From Numericana

2 . About Ferrers Diagram

3. An interesting paper that talks about fast algorithms for generating integer partitions.

Thus with these concepts code below displays a Ferrer’s diagram for a given input number and also generate the table using the generate function

#include<stdio.h>
#include<stdlib.h>
#define false 0;
#define true 1;
#define Min(x,y) ((x<y)?x:y)
typedef struct partitionnode
{
int m;
int numparts;
int parts[101];
} partition;
int Pn[40][40];
int P[50];
void output(partition a)
/*print out the partition a*/
{
int i,j;
printf("%d = ",a.m);
for(i=1;i<=a.numparts;i=i+1)
{
j = a.parts[i];
printf("%d",j);
if (i != a.numparts)
printf("+");
}
}
void RecPartition(partition a, int m, int B, int N)
/** generate all partitions with largest part of size at most B
** recursive procedure used in other procedures
*/
{
int i;
if(m==0)
{
a.numparts = N;
output(a); printf("\n");
}
else
{
for (i=1;i<=Min(B,m);i=i+1)
{
a.parts[N+1] = i;
RecPartition(a,m-i,i,N+1);
}
}
}
void GenPartitions(int m)
/*generate all partitions of m*/
{
partition a;
a.m = m;
RecPartition(a,m,m,0);
}
void EnumPartitions2(int m)
/*compute the partition numbers P[i] for i <= m*/
{
int i,j,sum,omega,omega2,sign;
P[0] = 1;
P[1] = 1;
for (i=2;i<=m;i=i+1)
{
sign = 1;
sum = 0;
omega = 1;
j = 1;
omega2 = omega+j;
while(omega <= i)
{
if(sign==1)
sum = sum + P[i-omega];
else
sum = sum - P[i-omega];
if(omega2 <= i)
{
if(sign==1)
sum = sum + P[i-omega2];
else
sum = sum - P[i-omega2];
}
omega = omega + 3*j+1;
j = j+1;
omega2 = omega+j;
sign = 0 - sign;
}
P[i] = sum;
}
}
int main()
{
int m,n,i,j,r,s,num;
int flag;
partition a;
char junk;
printf("Enter the Number : \n");
scanf("%d",&m);
printf("Ferrers Diagram with m=%d\n\n",m);
GenPartitions(m);
printf("\nEnd of Ferrers. Press enter to get the table\n"); scanf("%c",&junk);
printf("Table with all possible combinations with m=%d \n\n",m);
EnumPartitions2(m);
printf(" i |"); for(i=1;i<=m;i=i+1) printf("%5d", i ); printf("\n");
printf("-----|"); for(i=1;i<=m;i=i+1) printf("-----"); printf("\n");
printf("P[i] |"); for(i=1;i<=m;i=i+1) printf("%5d",P[i]); printf("\n");
printf("\nPress Enter to Exit\n"); scanf("%c",&junk);
return(0);
}

I have made minor modification to code already available here . The main intention here is only educational. I was unable to identify the exact author here and give author due credit.

OUTPUT:

laptop:~/code$ ./a.out

Enter the Number :

4

Ferrers Diagram with m=4

4 = 1+1+1+1

4 = 2+1+1

4 = 2+2

4 = 3+1

4 = 4

End of Ferrers. Press enter to get the table

Table with all possible combinations with m=4

i | 1 2 3 4

—–|——————–

P[i] | 1 2 3 5

Press Enter to Exit

laptop:~/code$ ./a.out

Enter the Number :

7

Ferrers Diagram with m=7

7 = 1+1+1+1+1+1+1

7 = 2+1+1+1+1+1

7 = 2+2+1+1+1

7 = 2+2+2+1

7 = 3+1+1+1+1

7 = 3+2+1+1

7 = 3+2+2

7 = 3+3+1

7 = 4+1+1+1

7 = 4+2+1

7 = 4+3

7 = 5+1+1

7 = 5+2

7 = 6+1

7 = 7

End of Ferrers. Press enter to get the table

Table with all possible combinations with m=7

i | 1 2 3 4 5 6 7

—–|———————————–

P[i] | 1 2 3 5 7 11 15

For Perl coders:

There exists a Integer::Partition module. It implements two algorithms from this paper

For Python coders:

There exists an active state discussion

I had a good learning session , hope you did. Hope this article has provided a one stop resource on this topic.

Thanks for Reading !

### Like this:

Like Loading...

*Related*

Hello,

Its a nice work. I am also doing research in Theory of Partitions.

I have some doubts regarding this. Shall we share our ideas.

Please do communicate me through my e-mail: raghava.srinivasa@gmail.com

Regards,

SRINIVASA RAGHAVA. K

Sure i have sent test mail. Probably i can add to this article your ideas and doubts !

how to partition a number if the sequence of number should be in a increasing order i,e 7 into 3 parts 1,2,4 or 8 [1,2,5 ][1,3,4] just plz give me the recurrence relation f(n,k) where n is number k is the number of partition

Let f(n,k) denote the number of ways of partitioning n into exactly k distinct parts.

Then f(n,k) = P(n-

_{k}C_{2},k)where P(n,k) = P(n-1,k-1) + P(n-k,k)

with P(n,k)=0 for k>n and P(n,n) =1 and P(n,0) = 0

P(n,k) denotes the number of ways of writing n as a sum of exactly k terms or, equivalently, the number of partitions into parts of which the largest is exactly k

so for P(5,3) = 2 , since the partitions of 5 of length 3 are {3,1,1} and {2,2,1} and and the partitions of 5 with maximum element 3 are {3,2} and {3,1,1}

Thus let us take n = 8 and partition it into 3 parts in increasing order i.e distinct 3 parts

f(n,k) = P(8-(3), 3) = P(5,3) = 2

Note :

_{3}C_{2}= 3so u got the 2 parts with distinct increasing elements. We only got the count , you might want to find out the exact sets though

I think I was asked this theorem in a Google interview :O Given a number print all sequences of numbers which sum up to k.

k =1 , then {1}

k = 2, then {1+1}

k = 3. then {1+2, 2+1, 1+1+1}

k = 4, then {1+1+1+1, 1+3, 3+1, 2+2}

I could not give a solution which did not generate duplicates. The interviewer, suggested that there could be a bottom-up strategy of finding the # of partitions.