Author |
Topic: Partitioning the array (Read 1221 times) |
|
harish
Newbie
Gender: 
Posts: 11
|
 |
Partitioning the array
« on: Nov 23rd, 2009, 6:38pm » |
 Quote  Modify
|
Sorry if this topic was discussed before.
I have searched for similar topics but didn't find any appropriate result.
You are given an array containing Integers.
Partition the array into two sub-arrays (can be of different size) such that the difference between the averages of two sub-arrays is minimum.
Is there a polynomial time algorithm for this?
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Partitioning the array
« Reply #1 on: Nov 24th, 2009, 6:12am » |
Quote Modify
|
Having well known NP complete problems of 2 thieves ... to divide list of numbers to two lists of equal sum. You can add same number of zeros to the list without changing solvability so the resulting list length is even.
Add some more zeros to make the list of length 2p-2 for a large prime number p.
Adding a big constant c to all numbers on the list does not change the solvability, but the solution divides list to equaly sized lists as well now. Add two equal huge numbers to the list such that the total sum becomes 2kp+2 for an arbitrary positive integer k. Resulting list can be divided into sublists of same average exactly when the original problem is solvable. (The average k+1/p cannot be obtained by average of smaller then p whole numbers).
So such algorithm costs 1 000 000$ 
on Dec 1st, 2009, 11:31am, brute wrote:
The answer is "No.".
Simillar task would be to find an index i such that the average of first i elements is as close to average of remaining elements. But this is clearly polynomial as there is only linear number of choices.
[edit]
If you wanted to do it as fast as possible you could compute all the averages from each end in O(n) total time using flying sums from the end. Unfortunately you get them in opposite order so you need O(n) extra storage to compute their differences and find the minimal one ... and if the original array is read/write, you can rewrite by flying sums from one direction and compute flying sums of the differences from the other direction (what actually telescopes to one difference) this allows you to compute the differences of averages in the second pass. During the second pass you can return the array to the original state as well.
... O(n) total. ... what is probably what is mentioned by Aryabhatta ...
[/edit]
|
| « Last Edit: Jan 14th, 2010, 6:20am by Hippo » |
IP Logged |
|
|
|
abhijeet
Newbie
Gender:
Posts: 3
|
|
Re: Partitioning the array
« Reply #2 on: Nov 25th, 2009, 9:04am » |
Quote Modify
|
There are ways to do it. For all positive #'s in an Array.
1) Using extra space.
Start multiplying from the beginning. Store the cumulative product in an Auxillary Array. When you reach the end. Take the final product and search for the product which is half of it. If you find it, you need to partition Arrays from this location. If NOT than there will be two no's in the Array which will be close to the Half select the one which is closest to the half and partition from there.
2. Multiply the first half. Multiply the second half. If they are equal, this is the partition. Else store the difference d1.
If NOT. Multiply the first Half with the first number in second half. Divide the second half with the first number in 2nd Half. Subtract them from each other and store the result d2.
Now Divide the first half with the last element in the first half. Multiply the second half with the last element in first half. Subtract them from each other, store the result in d3.
If d3 is least, let the last element of first half be the first element of second half and reduce first half by one index. REPEAT the process.
If d2 is least, so similar increase first half, decrease second half etc etc. REPEAT the process.
IF d1 is least , you have the answer.
|
|
IP Logged |
|
|
|
Lol
Newbie
Gender:
Posts: 13
|
|
Re: Partitioning the array
« Reply #3 on: Dec 1st, 2009, 11:31am » |
Quote Modify
|
any more suggestions ??
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Partitioning the array
« Reply #4 on: Dec 1st, 2009, 10:30pm » |
Quote Modify
|
Quote:
Start multiplying from the beginning
|
|
What will happen if array containing large number of elements?
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Partitioning the array
« Reply #5 on: Jan 5th, 2010, 10:38pm » |
Quote Modify
|
I have written this program and it seems to work.
Code:
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
int a[100];
int j=0;
int i=0;
double firstavg,secondavg;
for(i=0;i<100;i++)
{
a[i] = rand()%100;
}
firstavg=0.0;
secondavg=0.0;
for(i=0,j=10;i<=j;)
{
if(firstavg < secondavg)
{
i++;
firstavg = ((firstavg*i)+a[i]);
firstavg /= (i+1);
}
else
{
j--;
secondavg = ((secondavg*j)+a[j]);
secondavg /= (j-1);
}
printf("%lf %lf\n",firstavg,secondavg);
}
}
|
|
Is this correct?
PS: somehow the formatting is not coming correctly(for j++)..any suggestions..
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Partitioning the array
« Reply #6 on: Jan 6th, 2010, 1:44am » |
Quote Modify
|
Well, you never consider the first element (because you increment i before doing anything with it), and ignore everything from the 10th onwards (because you work from j=10 downwards, decrementing before doing anything with it). You can even use the same element in both arrays (because you still do something when i=j, both of which will have been used already).
And even aside from that, I don't think the basic idea behind it works. Because you don't necessarily increase an average by adding more elements to it. Consider for example the array [2,0,4]; you need to split it into [2] and [0,4], but you would add the 0 to the 2, because 2 < 4.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Partitioning the array
« Reply #7 on: Jan 6th, 2010, 7:39am » |
Quote Modify
|
As Hippo said, it is NP complete. (http://en.wikipedia.org/wiki/NP-complete)
If you think you came up with a polynomial time algorithm for this, I suggest you look closely...
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Partitioning the array
« Reply #8 on: Jan 13th, 2010, 1:33am » |
Quote Modify
|
Can't we use the greedy algorithm to partition the arrey to minimise the sum of elements (for average, we can add 0 value elements to one of the set), as to take all the elements in descending order and put element one by one in the set which is having lesser value.
If no (because the problem is NP-complete  ), what can be the example to refute the optimal case.
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Partitioning the array
« Reply #9 on: Jan 13th, 2010, 4:23am » |
Quote Modify
|
Using extra space...
Lets say that the array is of size n....
take another array of size n and start storing in the following manner...
newarr[k] = avg from arr[0] to arr[k]
to find the avg till kth elem, avg till (k-1)th elem can be used to reduce the number of computations
and 1 more such array
newarr2[k] = avg from arr[k] to arr[n-1]
once this is one it is a simple problem...
u have to compare newarr[k] with newarr2[k]...the diff must be min
Overall time complexity -> 3*O(n)
Overall space complexity -> 2*O(n)
|
| « Last Edit: Jan 13th, 2010, 4:24am by pscoe2 » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Partitioning the array
« Reply #10 on: Jan 13th, 2010, 5:13am » |
Quote Modify
|
This would assume the sub-arrays are contiguous. I am not sure it was requested, but to be fair it wasn't specified precisely.
Most so far have interpreted it in the sense of set theory, where the elements are added to the one or other sub-array independently.
|
|
IP Logged |
|
|
|
bmudiam
Junior Member
Gender:
Posts: 55
|
|
Re: Partitioning the array
« Reply #11 on: Jan 13th, 2010, 11:59am » |
Quote Modify
|
on Jan 13th, 2010, 5:13am, Grimbal wrote:This would assume the sub-arrays are contiguous. I am not sure it was requested, but to be fair it wasn't specified precisely.
Most so far have interpreted it in the sense of set theory, where the elements are added to the one or other sub-array independently.
|
|
Is it still NP-Complete, if the elements in each sub-array are contiguous?
|
|
IP Logged |
“Nobody can go back and start a new beginning, but anyone can start today and make a new ending.” - Maria Robinson
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Partitioning the array
« Reply #12 on: Jan 13th, 2010, 1:04pm » |
Quote Modify
|
but the assumption i have taken is tht the sub arrays create the final array...
That is...the main array was broken into 2 sub-arrays...
u get wht i understood from the question
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Partitioning the array
« Reply #13 on: Jan 13th, 2010, 1:18pm » |
Quote Modify
|
on Jan 13th, 2010, 11:59am, bmudiam wrote:
Is it still NP-Complete, if the elements in each sub-array are contiguous? |
|
No. Then you have a polynomial time algorithm, as there are at most n partitions and for each partition you can find the value required in O(n) time.
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Partitioning the array
« Reply #14 on: Jan 13th, 2010, 1:21pm » |
Quote Modify
|
Yup...it will be an O(n2) time complexity
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Partitioning the array
« Reply #15 on: Jan 13th, 2010, 1:25pm » |
Quote Modify
|
on Jan 13th, 2010, 4:23am, pscoe2 wrote:Using extra space...
Lets say that the array is of size n....
take another array of size n and start storing in the following manner...
newarr[k] = avg from arr[0] to arr[k]
to find the avg till kth elem, avg till (k-1)th elem can be used to reduce the number of computations
and 1 more such array
newarr2[k] = avg from arr[k] to arr[n-1]
once this is one it is a simple problem...
u have to compare newarr[k] with newarr2[k]...the diff must be min
Overall time complexity -> 3*O(n)
Overall space complexity -> 2*O(n) |
|
You can do it without the extra arrays, if you are willing to make two passes.
|
|
IP Logged |
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Partitioning the array
« Reply #16 on: Jan 13th, 2010, 1:29pm » |
Quote Modify
|
on Jan 13th, 2010, 1:25pm, Aryabhatta wrote:
You can do it without the extra arrays, if you are willing to make two passes. |
|
Ohh...i realise now...even no extra pass is req.
I can compare directly instead of creating the second array...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print