Printable View
I'm basically looking for a good algorithm or method to do the following:
I have 10 numbers, you can use List<Integer> or int[] or what ever u want.
I want to sort the 10 numbers so the sum of the first 5 is approximately (or exactly if possible) equal to the sum of the last 5. The sum of the first 5 must be as close as possible to the sum of the last 5.
How can I do that?
Thanks.
pseudo code,
place largest number in group 1, then next largest in group 2, then next in group 2, then next in group 1... do this until you run out of numbers, then add up group 1 and then add up group 2... it seems to me since you have to have 5 numbers in each group then it probably won't be equal all the time. here's an example.
1,2,3,4,5,6,7,8,9,10
Group 1 = 10,7,6,3,2 = 28
Group 2 = 9,8,5,4,1 = 27
and this seems to be right being that both groups add up are an odd number meaning you can't split them equally.
hope this helps, and i always appreciate comments.
i think this greedy algorithm is more suitable, but don't know if it's correct.
Code:for each item in input list
if total of list a > total of list b
then add current item to list b
else add current item to list a
unfortunately the greedy algorithm would work however the amount of checks that it would have to reproduce would be O(n^2) and i believe if you could sort the list and then do the split, mathimatically it works out, and programmatically it comes out to sort time + n which is O(n + n log n) time. which is O(n log n) time :0
the sort should be fairly simple since it's only 10 numbers, and the grouping them will be simple also. adding them up will take no time also :) it's a quick math algorithm that might actually already been proven somewhere :)
and i just relooked at what emceenugget posted a bit better, 1 pass through the loop means you have to add group a and b each, and then re-add item to a group with a check on top of it. 4 operations per item in the list.
still isn't bad.
if you can get passed the items being sorted then it's 1 operation per item. so it could be better but all depends on sorting i suppose.
so good call emceenugget :) but either way i think could work because of the small list size.
oh yeah. forgot about that i can't assume the list is sorted. d'oh.
i found this interesting and thought i'd give it a try.
* Assume a sorted int[10].
I used a for loop.
if i is evenNumber, then copy n[i] and n[last-i] to group1,
else copy to group2.
but if i is middle values, then one goes to group1, and next goes to group2.
so assuming numbers are 1 - 10,
group1 is: 1,10,3,8,5 = 27
group2 is: 2, 9,4,7,6 = 28
there's more effecient ways, more research, more research...
edit: don't really work when numbers duplicates as in 1,1,1,2,3,3,3,3,5,5,5
well i just realized that my algorithm is broken in that if you have a number that's really big that it'll add on everything else to the second list regardless of balancing the amount of items in it. i'd say once one side is full to add the rest onto the remaining list, but i don't think that's complete yet either.
oh! same applies to mine...
From: A fair split? Number partitioningQuote:
... This is the number partitioning problem, a classic and surprisingly difficult problem in computer science. In particular, it is NP-complete; it belongs to a category of problems for which no known algorithm can guarantee a resolution in a reasonable time (bounded by a polynomial in their size). ...
EDIT:
jasonre's algor. is pretty good except when used on very large numbers. see here:
* Code tobe shown after OP shows his...Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34
group1: 34, 20, 13, 9, 6
group2: 30, 23, 12, 10, 3
SUM-G1: 82
SUM-G2: 78
Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7
group1: 15, 14, 12, 6, 4
group2: 15, 15, 9, 7, 3
SUM-G1: 51
SUM-G2: 49
Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209
group1: 228, 209, 179, 58, 48
group2: 225, 209, 141, 93, 11
SUM-G1: 722
SUM-G2: 679
Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964
group1: 3752, 1964, 1388, 739, 234
group2: 2474, 2082, 1129, 821, 201
SUM-G1: 8077
SUM-G2: 6707
Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7
group1: 600, 15, 15, 7, 4
group2: 15, 15, 15, 9, 3
SUM-G1: 641
SUM-G2: 57
using jasonre's algo. I added an if statement before splitting the nums into 2 groups. like this:
where sum(n) is the remaining queue. and max is the current largest number.Code:if((sum(n) < max)&&(!(i==LAST))){
and that made a huge difference in the results:
Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34
group1: 34, 20, 13, 9, 6
group2: 30, 23, 12, 10, 3
SUM-G1: 82
SUM-G2: 78
Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7
group1: 15, 14, 12, 6, 4
group2: 15, 15, 9, 7, 3
SUM-G1: 51
SUM-G2: 49
Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209
group1: 228, 209, 179, 58, 48
group2: 225, 209, 141, 93, 11
SUM-G1: 722
SUM-G2: 679
Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964
group1: 3752, 1964, 1388, 739
group2: 2474, 2082, 1129, 821, 201, 234
SUM-G1: 7843
SUM-G2: 6941
Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7
group1: 4, 9, 15, 15, 3, 15, 15, 15, 7
group2: 600
SUM-G1: 98
SUM-G2: 600
well the only problem with that last part is that when the problem was first proposed, it was stated that there must be 5 numbers in each group. therefore you'll have to dis-include any of the last post that have 6 numbers in 1 group and 4 in the other, or 1 number in 1 group and 9 in the other. but if this is what you meant, i believe the algorithm would be just a tad different than my first post. I could probably figure that one what if that's what you meant but the check you through in there will be needed for sure. let me know..
oh, haha got too into it, forgot about the 5 per group limit.
actually, since the limits are fixed (10num, 5/g), i think its better to check for combinations of 5 per group. then check the difference between each combination for the smallest value. the two groups w/ the smallest diff will be the one desired. what's YHO on this?
np-complete problem, eh? i think we should all just give ourselves a pat on the back and stop trying =p
that depends on the size. its only 10 numbers. I CAN TAKE IT!!
Well i don't think it's np-complete because as long as you have the size, and they are ordered then move 1 in to one group then 2 into the next, 2 into the next so on and so forth and having 2n nodes, then it isn't hard to add up the result. don't doubt it's a hard problem though. however if the 2 group sizes aren't equal then yes it could be quite a hard problem and maybe then np-complete.
I don't think you want to check each of the combinations of numbers, yes 10 numbers a computer could do it, however 20 numbers a computer might fail big time. that's because the combination of numbers would 10c5 and 5c5 however when we start thinking about 20c10 and 10c10 we are dealing with numbers upward of 20! mean huge...
all i did was think about it, if i place the largest number in the first group. then the next largest number has to be in the 2nd group.... next largest number belongs in the 2nd group because it's already smaller than the first group... but then the next number goes in the 1st...
now for the 10,10,10,20,20,30,30,30,400,500
grp 1: 500,30,30,10,10
grp 2: 400,30,20,20,10
but we can already see that a problem like this won't work. here's where that check comes into play that i mentioned in the post a little earlier. if ( sum(grp1) - sum(grp2) > nextValue ) then add lowest group, and do this till max number of items are in grp2. I think that will finish it up.
yeah jasonre, you're right. it worked out nicely. (still need to test w/ other number combos. thats for later...)
* src will be shown after OP shows his...
here's the pseudo code:Code:[B]Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10[/B]
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
[B]Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1[/B]
group1: 10, 7, 6, 3, 2
group2: 9, 8, 5, 4, 1
SUM-G1: 28
SUM-G2: 27
[B]Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34[/B]
group1: 34, 20, 12, 10, 3
group2: 30, 23, 13, 9, 6
SUM-G1: 79
SUM-G2: 81
[B]Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7[/B]
group1: 15, 15, 9, 7, 4
group2: 15, 14, 12, 6, 3
SUM-G1: 50
SUM-G2: 50
[B]Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209[/B]
group1: 228, 209, 141, 93, 58
group2: 225, 209, 179, 48, 11
SUM-G1: 729
SUM-G2: 672
[B]Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964[/B]
group1: 3752, 1964, 1129, 234, 201
group2: 2474, 2082, 1388, 821, 739
SUM-G1: 7280
SUM-G2: 7504
[B]Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7[/B]
group1: 600, 9, 7, 4, 3
group2: 15, 15, 15, 15, 15
SUM-G1: 623
SUM-G2: 75
seems to be getting better results from the second one...Code:nextVal = findNextLargest();
if(gp1-gp2 != nextVal && both groups not filled){
[I]// also works w/: if(both groups not filled){
// need more test on this.[/I]
if(sum(gp1) < sum(gp2)) add next to gp1;
else add next to gp2;
}
else{
if(gp1 is not filled) add next to gp1;
else add next to gp2;
}
** Oh my head... Too much math in one day...Code:[B]if(gp1-gp2 != nextVal && both groups not filled){[/B]
Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209
group1: 228, 209, 141, 93, 58
group2: 225, 209, 179, 48, 11
SUM-G1: 729
SUM-G2: 672
[B]if(both groups not filled){[/B]
Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209
group1: 228, 209, 141, 93, 48
group2: 225, 209, 179, 58, 11
SUM-G1: 719
SUM-G2: 682
I test out the combo method and its PERFECT!! I used a 10C5 combination generator to get all the possible combos, which is 252. Then filter out the results several times to get the final two groups needed. Because its only 10C5, I didn't notice any difference in speed.
Here are the results.
Code:Set1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
group1: 1, 2, 5, 9, 10
group2: 3, 4, 6, 7, 8
SUM-G1: 27
SUM-G2: 28
Set2: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
group1: 10, 9, 6, 2, 1
group2: 8, 7, 5, 4, 3
SUM-G1: 28
SUM-G2: 27
Set3: 10, 13, 23, 6, 20, 30, 12, 3, 9, 34
group1: 10, 13, 20, 3, 34
group2: 23, 6, 30, 12, 9
SUM-G1: 80
SUM-G2: 80
Set4: 6, 4, 9, 14, 12, 3, 15, 15, 15, 7
group1: 6, 14, 12, 3, 15
group2: 4, 9, 15, 15, 7
SUM-G1: 50
SUM-G2: 50
Set5: 93, 58, 141, 209, 179, 48, 225, 228, 11, 209
group1: 93, 141, 209, 48, 209
group2: 58, 179, 225, 228, 11
SUM-G1: 700
SUM-G2: 701
Set6: 2474, 1129, 1388, 3752, 821, 2082, 201, 739, 234, 1964
group1: 2474, 1388, 821, 739, 1964
group2: 1129, 3752, 2082, 201, 234
SUM-G1: 7386
SUM-G2: 7398
Set7: 600, 4, 9, 15, 15, 3, 15, 15, 15, 7
group1: 600, 4, 9, 3, 7
group2: 15, 15, 15, 15, 15
SUM-G1: 623
SUM-G2: 75
Set8: 1, 1, 1, 2, 2, 2, 3, 3, 4, 5
group1: 1, 1, 1, 4, 5
group2: 2, 2, 2, 3, 3
SUM-G1: 12
SUM-G2: 12
yea the combo method works, and you won't find a difference in speed unless you were on a very slow computer or if you try to use more numbers to sort. for instance, instead of 10 numbers, use 100 numbers, and 50 in each group. and just for the fun of it, use the fibonacci sequence for the numbers. that's 1,1,2,3,5,8,13,21,34,...
you might find it a bit more difficult for the combination method. i think that would be fun to see the difference. and to verify how much the cpu works, add a system.out of the time stamp just before and after it goes into the work of both ways in which you do it. let me know the results, i'm curious :)
oh yes and make sure it's sorted highest number backwards.
if you need help generating the sequence, its
ArrayList<Double> a = new ArrayList<Double>();
double n = 1;
double m = 1;
a.add(n);
a.add(m);
for (int i = 1; i < 99; i++) {
double o = a.get(i) + a.get(i-1);
a.add(o);
}
for (int i = 0; i < a.size(); i++) {
System.out.println(a.get(i));
}
then reorganize them the other direction.
k, that sounds like a fun project for the weekend. right now, both algo. are written procedural using int arrays, so i'll first need to reorganize it more OOP. then i'll test for fibonacci# from H-L and also from L-H. and see which has the better speed/result.
mind posting your code so i can give it a shot? i'm kind of bored here at work.