Page 2 of 3 FirstFirst 123 LastLast
Results 21 to 40 of 57
  1. #21
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    no i don't mind. but i don't want to influence perito to much in his homework assignment. so i'll pm you instead. but the combo gen is a pretty large file. so you'll prob get several pms from me. warning, its sloppy coding...

    edit: hmmm... you have PM turned off?
    Last edited by angryboy; 02-06-2009 at 09:31 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default

    my apologies, i did have it turned off, i believe i have it turned on now :)

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

    Default

    this topic is officially hijacked...

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

    Default

    lol, what happened to perito?
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default

    UPDATE!!! LOL. Its NOT possible. the max i could go up to was 20C10. Anything larger than that and the jvm will throw "OutOfMemoryError" exception.
    Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at BruteForce.getAllCombos(BruteForce.java:66)
    at BruteForce.<init>(BruteForce.java:48)
    at NPMain.main(NPMain.java:8)
    output from 20C10. no speed difference from 10C5.
    Java Code:
    [B]Set:    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 
                  377, 610, 987, 1597, 2584, 4181, 6765[/B]
    
    group1:   1, 2, 3, 8, 13, 34, 55, 377, 1597, 6765
    group2:   1, 5, 21, 89, 144, 233, 610, 987, 2584, 4181
    SUM-G1:   [B]8855[/B]
    SUM-G2:   [B]8855[/B]
    Here's the output using jasonre's algo. 20-10.
    Java Code:
    [B]Set:    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 
                  377, 610, 987, 1597, 2584, 4181, 6765[/B]
    
    group1:   6765, 1597, 377, 89, 21, 5, 3, 2, 1, 1
    group2:   4181, 2584, 987, 610, 233, 144, 55, 34, 13, 8
    SUM-G1:   [B]8861[/B]
    SUM-G2:   [B]8849[/B]
    But it can go as large as 90-45, before overflow of type long. What's even more amazing is that there's no speed diff. (non that i could tell anyways...)
    Set: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
    4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
    832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
    63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170,
    1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
    53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879,
    956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842,
    10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141,
    117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393,
    1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757,
    8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906,
    61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585,
    420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189,
    2880067194370816120


    group1: 2880067194370816120, 679891637638612258, 160500643816367088, 37889062373143906,
    8944394323791464, 2111485077978050, 498454011879264, 117669030460994, 27777890035288,
    6557470319842, 1548008755920, 365435296162, 86267571272, 20365011074, 4807526976,
    1134903170, 267914296, 63245986, 14930352, 3524578, 832040, 196418, 46368, 17711, 10946,
    6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1


    group2: 1779979416004714189, 1100087778366101931, 420196140727489673, 259695496911122585,
    99194853094755497, 61305790721611591, 23416728348467685, 14472334024676221,
    5527939700884757, 3416454622906707, 1304969544928657, 806515533049393, 308061521170129,
    190392490709135, 72723460248141, 44945570212853, 17167680177565, 10610209857723,
    4052739537881, 2504730781961, 956722026041, 591286729879, 225851433717, 139583862445,
    53316291173, 32951280099, 12586269025, 7778742049, 2971215073, 1836311903, 701408733,
    433494437, 165580141, 102334155, 39088169, 24157817, 9227465, 5702887, 2178309, 1346269,
    514229, 317811, 121393, 75025, 28657

    SUM-G1: 3770056902373205253
    SUM-G2: 3770056902373141175
    Last edited by angryboy; 02-07-2009 at 11:13 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  6. #26
    fishtoprecords's Avatar
    fishtoprecords is offline Senior Member
    Join Date
    Jun 2008
    Posts
    571
    Rep Power
    7

    Default

    Why not just sort the list, Java has nice sort functions, n(ln n) performance, beats the hell out of n^2 if N is big, and if its small, why care?

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

    Default

    This is NOT about sorting numbers.
    well, the title is misleading. it should've been "partitioning" 10 numbers.

    right now i'm thinking of a way to break down the combinations into several stages. because i used arrays, so 10C5 = 252 possibilities would be int[252]. but 100C50 would be a huge array. I think arraylist would still run out of memories. So, is there a way to generate the combinations, pause, calculate for first batch, garbage collect, then proceed to another batch of combinations...?
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  8. #28
    fishtoprecords's Avatar
    fishtoprecords is offline Senior Member
    Join Date
    Jun 2008
    Posts
    571
    Rep Power
    7

    Default

    Quote Originally Posted by angryboy View Post
    the title is misleading. it should've been "partitioning" 10 numbers.
    Duh.

    How about this. Setup an arraylist with ten slots, set a variable to the tenth highest number.

    Loop through your whole list,
    if ( entry > tenthHigherNumber,) {
    tenthHigherNumber = entry;
    add entry to arraylist
    if arraylist.length() > 10;
    remove smallest entry

    }

    This is o(1)
    Whether you keep the arraylist sorted or not is an exercise to the student.

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

    Default

    A couple of things, I'm back at work now so i can respond hehe... I'm not suprised that the combination way is much slower or crashes when there are more than 20 nodes. Good Work angryboy!

    Yes this wasn't not suppose to be a sort exercise, in fact i think i stated in post #2 that the list that my algo would be working with must in fact be sorted. and I believe i stated that it was O(n ln n) also :) There's a couple of things that would speed the process up though, try to remove operations from the loop. However i think we did a good job to keeping them small.

    After angryboy had given me his code, I added a timestamp output before and after the processes. Each of the 10s came out to be about 15 ms. I however haven't really had time to add it to the fibonacci sequence yet, but I think there may be a way to extend the overflow so it doesn't crash once the numbers get that large.

    :) Good work angryboy!

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

    Default

    well, i rewrittened Test4.java to use arrarylist<biginteger> and was able to cal for fib sequence of 100#s. the time's about 8ms. at 1000#s, the timing was 701ms. (excluding printlns.) This is tested on an amd 1ghz. the difference in the group sum grows larger as the #s gets larger.

    Still trying to fix the combo generator so i can traverse the indices backwards. Then I wouldn't need to use a 2d array to hold all the data. and that should fix the mem error. but my math ain't the good...

    here's the link to the combo gen that i used: Combination Generator
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  11. #31
    hendrix79 is offline Member
    Join Date
    Dec 2008
    Posts
    28
    Rep Power
    0

    Default

    Well... recursion is a big pain with algorhythm complexity.

    I think that the best solution is to have a list... you can split it in two (one that contains the middle of the max amount of numbers starting from the lowest and the other one starting by the highest). So you just have to put the list together in order.

    Or you can create a stack: you can pop the number from a list and push it into another... and if the number 'popped out' is bigger than the one just 'pushed-in' the other list you put it into the bottom. A sort of FIFO stack.

    Maybe it's a little bit complex in implementing it, but maybe it's light when sorting out.

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

    Default part1 is done...

    Not too familiar w/ JCF... I had that idea in mind, but thought that two objects of arraylist would have greater overhead than a 2D arrays. Which would still result in memory error. not too sure, will it?

    Anyways, after messing w/ the combo gen for hours with no luck, i've found a link to MSDN on wikipedia "Combinadic" page with the code i needed. And have successfully ported it over to Java from C#. next thing to do is to rewrite BruteForce.java and hope the jvm don't run out of ram.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default

    The biggest problem with the brute force method is the same as the famous traveling salesman problem. If you have to check every combination possible, it becomes impossible to do it for more than n nodes where n is a fairly small number. there might be a point where you get 20 numbers, or even 30 numbers but sooner or later, a computer just won't be able to do 31, because you are looking at 31! possibilities.

    however recursion is a great way to go, complex to the normal human mind, computers actually work faster with recursion. a computer will treat a method calling itself with simplicity and the benefits of recursion can be well seen by processing time, however not every case deserves to have recursion. But you will see why recursion is needed in this case, calling itself multiple times (a varied amount of times) shows the ! (factorial) part of combinations.

    And for the quote, "I think that the best solution is to have a list... you can split it in two (one that contains the middle of the max amount of numbers starting from the lowest and the other one starting by the highest). So you just have to put the list together in order. "
    I am not totally sure this works in every case, it may work in a couple of situations but trying to handle a problem without setting off certain situations. if we did that, then we'd have a NP-Complete problem as stated before. The reason why i would suggest that this isn't an NPC problem is because we know how much each group 1 and 2, MUST contain (n/2) nodes.
    Seriously come up with a more psuedo-code looking type of solution and we can put it into code, run it against some test and see how it works! So far we have 1 solution that works for 90 nodes+ and it's more of a good estimation type, and the other runs out of memory with only 20 nodes?

    I have an idea that I'm going to try and play with if i have time today that may make my algo a little bit more accurate, and hopefully more effeicient :)

    Anyway, Keep sending ideas.

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

    Default

    So i generated 1000 fibonacci numbers, and here's the results and i will refrain from posting the groups...

    [2/10/09 16:18:25:085 EST] 0000002f SystemOut O Start Time: 1234300705085
    [2/10/09 16:18:26:710 EST] 0000002f SystemOut O End Time: 1234300706710
    [2/10/09 16:18:26:710 EST] 0000002f SystemOut O 56898462699180136128761891276112087786372965176865 25657254331708834554626807299273507306466732093345 13918365211610443129316980264443450484847885868481 85281100536688224276786059186943804841966416193118 647930499 = 56898462699180136128761891276112087786372965176865 25657254331708834554626807299273507306466732093345 13918365211610443129316980264443450484847885868481 85281079863838825220322963867170966552601623847293 524701876
    [2/10/09 16:18:26:710 EST] 0000002f SystemOut O difference: 20672849399056463095319772838289364792345825123228 623

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

    Default

    Seriously come up with a more psuedo-code looking type of solution and we can put it into code, run it against some test and see how it works!
    This should be made into a forum contest!! haha.
    See who can come up w/ the best algorithm with:
    - the smallest sum difference.
    - the fastest speed. (depends on cpu...)

    + for fibonacci numbers from 1 to 100, 200, 500, and 1000.
    + for 100 random numbers of n digits.

    limited two members per group. register now!
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default Combine Method!

    For GroupSplit.java (use to be Test4.java), I've added a new method. Once the numbers are partitioned into two groups, i then swap (first element) and shift left (groupA only) to find one combo with a smaller sum-difference. its kind of like a mini-version of bruteforce. The results are getting close but not exact.

    Java Code:
    [B]20/10[/B]
    Diff:   2  -- Should be 0, old version is: 12
    Time:   0.03 secs
    [B]100/50[/B]
    Diff:   46,367  -- old version is: 196,417
    Time:   0.401 secs
    [B]200/100[/B]
    Diff:   7,778,742,048
    Time:   3.194 secs
    [B]500/250[/B]
    Diff:   36726740705505779255899442
    Time:   64.933 secs
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default

    hehe, yea the fibonacci sequence with 1000 numbers into 2 groups came out to be about 1 second. and the first 152 digits of the sum of each group are exactly the same. now a way to check it. the group that has the greater amount G1, if you take the two smallest numbers of that group, add them up, and then take the 2 smallest numbers that group G2, add them up.. if G1 < G2 then you should be able to swap the numbers that you just compared with each group. re-sum each group and re-compare the difference. gosh this is kind of confusing... i think i'll just do it and see what it comes out to :)

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

    Default

    Ok, i think i will make this statement but i can't prove it, it's more of a theory that i'm sure it can be proven. The difference of the sum of any two numbers in G1 and the sum of any two numbers in G2 will be smaller than the smallest number in G2. I might be getting my groups switched around but for the most part if logically that doesn't work with the Groups, just switch my G1's for G2's and vise-versa. Anyhow, if this "theory" fails then you can swap the 2 numbers from the 1 group with the other 2 numbers and the overall difference should be even closer.

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

    Default

    The difference of the sum of any two numbers in G1 and the sum of any two numbers in G2 will be smaller than the smallest number in G2.
    Had to read that several times, and still don't make sense to me... It failed when I tested it on this numbers.
    Java Code:
    G1: [[B]55, 13[/B], 3, 1, 1]
    G2: [[B]34, 21[/B], 8, 5, 2]
    SUM-G1: 73
    SUM-G2: 70
    55 + 13 = 68
    34 + 21 = 55 - 68 = 13.abs()

    smallest in G2 is 2.

    oh wait, or did you mean the smallest of the two numbers in G2? which is 21 in the case...
    but then:
    sumG1 - sumG2 = diff.abs();
    (13+3)-(21+8)= 13
    Last edited by angryboy; 02-12-2009 at 02:50 PM.
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

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

    Default

    well with your example i meant: 5+2 from group 2, and 1+1 from group 1 = 7 - 2 = 5 which is larger than the difference 73-70=3.

    if it looked like:
    G1: 55, 13, 8, 3, 1 = 80
    G2: 34, 21, 5, 2, 1 = 63
    difference = 17
    3 + 1 = 4
    2 + 1 = 3
    difference is 1
    1 is not greater than 17 therefore a number is wrong.. here's where the tricker part comes in... keep going up the line till you find the one that is just under 17, so.. the next one.
    8 + 3 = 11
    2 + 1 = 3
    difference = 8 not greater than
    13 + 8 = 21
    2 + 1 = 3
    difference is 17 which means we have a number in group 1 that should be in group 2.
    and swap it out for the lowest in group 1
    8 or 13, i'm working on a method to figure out which it is but i have like 2 minutes atm...
    8 is in fact the case... and swapped out for 1 and we see the results which you had before... it's kind of a verification that should be somewhat easy to check but a fun algo :) anyhow i'll get back to this in about a day or so... if you have questions ask..

Page 2 of 3 FirstFirst 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
  •