ISourceCode

Make the frequent cases fast and the rare case correct

Ferrers Partitions which are Palindromes

Firstly, Information about Ferrers diagram can be found in this previous article

A recursively palindromic (RP) word is one that is a palindrome and whose left
half-word and right half-word are each RP. Thus ABACABA is, and MADAM is not,
an RP word. – quoted from this Paper .

The objective of this puzzle is to find the total number of RP that can be formed from the integer partitions of a number
For example:
for number = 4
Ferrers Diagram

4 = 1+1+1+1
4 = 2+1+1
4 = 2+2
4 = 3+1
4 = 4

The total no of the RP partitions are 4
4
1+1+1+1
2+2
1+2+1

Note: every integer > 1 has at least two recursively palindromic partitions one consisting of all ones and a second consisting of the integer itself

Algorithm 1:

1 . Construct the Ferrer Diagram using the algorithm used in this article

2. For all Ferrers Partitions

3. Send every partition values to a function called PossiblePalindrome described in this article.

4. If successful, increment a counter

Algorithm 2:

1. F(N) is the no of RP’s of N

2. if N is even, put any even number K <= N in the center and then a RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F(N/2) = F(N-2) + F(N/2) (1 is the case where K = N)

3.if N is odd, put any odd number K <= N in the center and then RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F((N-1)/2) = F(N-1) (1 is the case where K = N)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int array[100];
int max;

int PalindromePartition(int val)
{
	int i;
	if(val <= max)
	{
		return array[val];
	}
	for(i = max+1; i <= val; i++)
	{
		if((i & 1) != 0)
		{
			array[i] = array[i-1];
		}
		else
		{
			array[i] = array[i-2] + array[i/2];
		}
	}
	max = val;
	return array[val];
}
int main()
{
	int num;
	printf("Enter the Number:\n");
	scanf("%d",&num);
	array[0] = array[1] = 1;
	max = 1;
	PalindromePartition(10);//compute for until 10 or any number
	printf("The total number of possible Palindrome partitions are %d\n",array[num]);
	return 0;
}

OUTPUT:

laptop:~/code$ ./a.out
Enter the Number:
7
The total number of possible Palindrome partitions are 6

Look at ferrers table for 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

It is evident visually that from these 15 partitions only 6 are RP.

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

It would be interesting to implement a function to print the RP in a formatted manner.

Thanks for Reading !

One response to “Ferrers Partitions which are Palindromes

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: