Saturday, March 23, 2013

Partition an array into 2 parts with equal average

we have to find partition such that average of two partitions are same, it seems that we need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total # of items.
Let S1 = sum of partition 1
n1 = # of items in partition 1
S2 = sum of partition 2
n2 = # of items in partition 2
S = S1+S2
n = n1+n2
Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2 = (S1+S2)/(n1+n2) = S/n
Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :

T[k][i][j] = T[k-1][n-1][j-item_i] || T[k][i-1][j]


An example to follow above idea: items = {2, 4, 4, 6, 6, 8}
N = 6, S = 30, Avg = 5
for k = 2, we can generate T[2][4][10] = 1
which implies Avg. of this partition = 10/2 = 5


TC would be O(N^2*S), space could be reduced to O(N*S).



public class Partition {

public static void main(String[] args) {
int [] A = {2, 4, 4, 6, 6, 8};
partitionEqualAvg(A);
}

public static void partitionEqualAvg(int [] A) {
int n = A.length;
int S = sumOfArray(A);
double avg = S/n;
int subsetLen = n/2;

boolean [][][] T = new boolean[subsetLen+1][n+1][S+1];

for (int i=0; i<=n; i++) {
T[0][i][0] = true;
}

for (int k=1; k<=subsetLen; k++) {
for (int i=1; i<n; i++) {
for (int j=1; j<=S; j++) {
if (A[i] <= j) {
T[k][i][j] = T[k-1][i-1][j-A[i]];
}
T[k][i][j] = T[k][i][j] || T[k][i-1][j];
if (T[k][i][j]) {
double tempAvg = (double)j/(double)k;
if (Math.abs((tempAvg - avg)) <= 0.0001 ) {
System.out.println("Partition 1: sum " + j + " of " + k +" items");
System.out.println("Partition 2: sum " + (S-j) + " of" + (n-k)+" items");
return ;
}
}
}
}
}
System.out.println("No partition with equal average possible!");
}

public static int sumOfArray(int [] A) {
int len = A.length;
int sum = 0;
for (int i=0; i<len; i++) {
sum += A[i];
}
return sum;
}
}

2 comments:

Unknown said...

Which language I can test above sample

Ram said...

@ali, Code is in Java...