ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to implement “Equal Sum Subsets” – For a sequence of numbers, find a subset[s](same order as original sequence) in which each subset has the same smallest sum

The problem and variations of the same has been frequently asked in competitions.

The goal of the program is to find equal sum subsets of a given sequence of numbers

For example :
Sequence : 3 1 3 7 5 2
Subsets : [3,1,3] [7] [5,2] with smallest possible sum of 7
If no such subset is possible the algorithm returns a subset which is the sequence itself i.e [3,1,3,7,5,2] with a sum of 21

Lets note down two important features
1. The sum has to be the smallest
2. The subset elements must be in sequence
input : 3 7 1 3 5 2 will not work as [3,1,3] is not in sequence.

ALGORITHM:
1. Calculate the total sum of the sequence
2. Read each element and assign it to a temporary sumA
3. check if the temporary sum is a factor of total sum
4. If it is check if remaining elements add up to be a factor
a. Do this by reading the remaining elements into another temporary sumB
if this sumB == sumA we get a subset
else the remaining set does not give factors
5. if the remaining set does not result in factor continue reading elements into sumA
6. Continue until sumB = sumA.

TRACE:
Let us trace inputs to clearly understand the strategy
input : 3 1 3 7 5 2
sum = 21
1. sumA = 3
2. sumA factor of 21, so check if remaining elements form subsets
3. sumB = 1
4. if ( sumB > sumA) return 0 (so that sumA can continue to take elements)
else (sumB == sumA) return 1
so , (1 > 3) returns 0
5. Now reads into sumA = 3+1 =4
6. sumA is not factor of 21 so continue reading
7. sumA = 3+1+3 = 7
8. sumA is a factor of 21, so check if remaining elements form subsets
9. sumB = 7 (remember everytime we enter to check remaining elements sumB is made 0)
10. if (sumB > sumA) sumB = 0 (this is indication that we have another subset)
11. continue with remaining sumB= 5
12. if (sumB > sumA) continue reading into sumB
13. sumB = 5+2 = 7 if (sumB == sumA) sumB=0 (indicated we have another subset)
14. if (sumB == 0) return true that we have the subset
15. Now equipped with the minimum sum value i.e sumA finding the subsets is a trivial matter. Steps 1 – 14 is only to find minsum we did not track the actual elements of the subset.

IMPLEMENTATION : in C

#include "stdio.h"

int data[100];
int sum = 0;
void partition(int minsum,int size);
void PrintPartition(int start,int end);
int main()
{
	int  i,size,minsum;
	printf("Enter the number of elements\n");
	scanf("%d",&size);
 	printf ("Enter the elements\n");
	for(i=0 ;i<size ;i++)
	{
		scanf("%d",&data[i]);
		sum+=data[i];	
	}
	minsum = LeastPartitionSum(size);
      	printf("The total smallest sum of equal partition is %d\n", minsum);
	printf("The partitions are : \n");
	partition(minsum,size);
  
   return 0;
}
/* Equipped with knowledge of minsum , find the exact elements */
void partition(int minsum,int size)
{
	int i,sum=0,count=0,start=0;	
	for (i =0 ;i < size ; i++)
	{
		sum+=data[i];
		count++;
		
		if(sum == minsum)
		{
			sum = 0;
			PrintPartition(start,count);
			start=count;		
		}
	}
} 
/* method to print the elements in readable format */
void PrintPartition(int start,int end)
{
	int i;
	printf("[");
	for ( i=start; i<end; i++)
	{
		if(i != end-1)
		{

			printf("%d,",data[i]);
		}
		else
		{
			printf("%d",data[i]);	
		}
	}
	printf("]\n");
}
/* method to find if remaining elements can be bunched to be factors of the total sum */
int CheckRemBunchSum(int BunchSum, int start, int size)
{
	int i, RemBunchSum;
	RemBunchSum = 0;
	for(i = start; i < size ; i++)
	{
		RemBunchSum += data[i];
		if(RemBunchSum > BunchSum)
      		{
         		return 0;
      		}
      		else if(RemBunchSum == BunchSum)
      		{
         		RemBunchSum = 0;
      		}
   	}
   	if(RemBunchSum != 0)
   	{
      		return 0;
   	}
   	return 1;
}

/* trying to find the first possible set of elements which are a factor of total sum */
int LeastPartitionSum(int size)
{
   int BunchSum, i; /*bunch sums over a loop until its a factor of total sum */
   for(i = 0, BunchSum = 0; (i < size) && (BunchSum <= sum/2) ; i++)
   {	
	BunchSum += data[i];
	if((sum % BunchSum) == 0)
	{   /* BunchSum divides sum, so lets go ahead and check if remaining elements are factors */
		if(CheckRemBunchSum(BunchSum, i+1, size))
		{
			return BunchSum;
	        }
	
      	}
   }
   /* if no subset is formed */
   printf("There is no subset formed. We have to consider the whole array as the set\n");
   return sum;
}

OUTPUT:

laptop:~/code$ ./a.out
Enter the number of elements
6
Enter the elements
3
1
3
7
5
2
The total smallest sum of equal partition is 7
The partitions are :
[3,1,3]
[7]
[5,2]

Now lets change the input to 3 1 3 6 6 2
laptop:~/code$ ./a.out
Enter the number of elements
6
Enter the elements
3
1
3
6
6
2
There is no subset formed. We have to consider the whole array as the set
The total smallest sum of equal partition is 21
The partitions are :
[3,1,3,6,6,2]

ADDITIONAL READING:

Related topics include NP complete problem termed Partition problem and Subset sum problem

These are problem usually solved used heuristic approach, especially for the subset sum problem that involves a greedy heuristic proposed by Kamarkar-Karp differencing algorithm

In my future posts i will post more detail of the partition and subset sum problem.

This Paper looks into various variations of the K- equal subset sum problems.

For now you might have seen how the problem statement is a heavy modification of the K- equal subset sum – NP complete problem. We made life easy by stating properties like same sequence and smallest sum with a condition that we can have the entire original sequence as a subset if we do not get any subset.

With above material,it would be interesting to brainstorm to solve the problem when there are potential correct subset with a jumbled up original sequence, [ 3 2 7 1 5 3] 😉

Thanks for reading !

2 responses to “Algorithm to implement “Equal Sum Subsets” – For a sequence of numbers, find a subset[s](same order as original sequence) in which each subset has the same smallest sum

  1. Vikas January 7, 2012 at 5:38 am

    I am doubtful for this solution in case when set is {5,5,5,2,2,2}
    When I executed the code, I expected it to provide me three sets of {5,2}
    Did I miss something?

    • chinmaylokesh February 14, 2012 at 3:40 am

      The resultant set {5,2} must be in sequence. This sequence will work

      laptop:~$ ./a.out
      Enter the number of elements
      6
      Enter the elements
      5
      2
      5
      2
      5
      2
      The total smallest sum of equal partition is 7
      The partitions are :
      [5,2]
      [5,2]
      [5,2]

      I have to modify to over come this discrepancy.

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: