Page 1 of 3 123 LastLast
Results 1 to 20 of 57
  1. #1
    perito is offline Member
    Join Date
    Feb 2008
    Posts
    9
    Rep Power
    0

    Default Sorting 10 numbers

    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.

  2. #2
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    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.

  3. #3
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    i think this greedy algorithm is more suitable, but don't know if it's correct.

    Java 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

  4. #4
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    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.
    Last edited by Jasonre; 02-04-2009 at 07:29 PM.

  5. #5
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    oh yeah. forgot about that i can't assume the list is sorted. d'oh.

  6. #6
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    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
    Last edited by angryboy; 02-04-2009 at 11:03 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  7. #7
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    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.

  8. #8
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    oh! same applies to mine...
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  9. #9
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    ... 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). ...
    From: A fair split? Number partitioning

    EDIT:
    jasonre's algor. is pretty good except when used on very large numbers. see here:
    Java 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
    * Code tobe shown after OP shows his...
    Last edited by angryboy; 02-05-2009 at 08:05 AM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  10. #10
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    using jasonre's algo. I added an if statement before splitting the nums into 2 groups. like this:
    Java Code:
    if((sum(n) < max)&&(!(i==LAST))){
    where sum(n) is the remaining queue. and max is the current largest number.
    and that made a huge difference in the results:
    Java 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
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  11. #11
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    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..

  12. #12
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    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?
    Last edited by angryboy; 02-05-2009 at 07:26 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  13. #13
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    np-complete problem, eh? i think we should all just give ourselves a pat on the back and stop trying =p

  14. #14
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    that depends on the size. its only 10 numbers. I CAN TAKE IT!!
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  15. #15
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    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.

  16. #16
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    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...
    Java 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
    here's the pseudo code:
    Java 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;
    }
    seems to be getting better results from the second one...
    Java 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
    ** Oh my head... Too much math in one day...
    Last edited by angryboy; 02-05-2009 at 11:17 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  17. #17
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    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.
    Java 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
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  18. #18
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    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.
    Last edited by Jasonre; 02-06-2009 at 08:38 PM.

  19. #19
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    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.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  20. #20
    Jasonre is offline Member
    Join Date
    Jan 2009
    Posts
    40
    Rep Power
    0

    Default

    mind posting your code so i can give it a shot? i'm kind of bored here at work.

Page 1 of 3 123 LastLast

Similar Threads

  1. Replies: 5
    Last Post: 02-07-2009, 07:48 AM
  2. printing two smallest numbers from a series of numbers
    By trofyscarz in forum New To Java
    Replies: 2
    Last Post: 10-14-2008, 11:46 PM
  3. sorting
    By jot321 in forum New To Java
    Replies: 18
    Last Post: 10-02-2008, 10:30 AM
  4. sorting problem
    By mcal in forum New To Java
    Replies: 1
    Last Post: 02-14-2008, 08:13 AM
  5. sorting JTable
    By mansi_3001 in forum Advanced Java
    Replies: 3
    Last Post: 08-10-2007, 06:29 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •