Skip to content

Integer Partition and Ferrers Diagram

January 26, 2011

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 !

About these ads
5 Comments
  1. SRINIVASA RAGHAVA permalink

    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

  2. sunny permalink

    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-kC2,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 : 3C2 = 3

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

  3. Lodu permalink

    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.

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

%d bloggers like this: