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 !