Results 21 to 40 of 57
Thread: Sorting 10 numbers
 02062009, 10:28 PM #21
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; 02062009 at 10:31 PM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02062009, 10:46 PM #22Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
my apologies, i did have it turned off, i believe i have it turned on now :)
 02062009, 10:48 PM #23Senior Member
 Join Date
 Sep 2008
 Posts
 564
 Rep Power
 9
this topic is officially hijacked...
 02062009, 10:54 PM #24
 02072009, 11:47 PM #25
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)
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 SUMG1: [B]8855[/B] SUMG2: [B]8855[/B]
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 SUMG1: [B]8861[/B] SUMG2: [B]8849[/B]
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
SUMG1: 3770056902373205253
SUMG2: 3770056902373141175Last edited by angryboy; 02082009 at 12:13 AM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02082009, 06:34 AM #26
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?
 02082009, 07:33 AM #27
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)
 02082009, 07:51 AM #28
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.
 02092009, 02:55 PM #29Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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!
 02092009, 07:20 PM #30
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 GeneratorUSE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02102009, 12:32 AM #31Member
 Join Date
 Dec 2008
 Posts
 28
 Rep Power
 0
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 'pushedin' 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.
 02102009, 06:15 AM #32
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)
 02102009, 02:52 PM #33Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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 NPComplete 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 psuedocode 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.
 02102009, 11:15 PM #34Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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
 02112009, 11:41 PM #35Seriously come up with a more psuedocode looking type of solution and we can put it into code, run it against some test and see how it works!
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)
 02122009, 05:18 AM #36
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 sumdifference. its kind of like a miniversion 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)
 02122009, 02:41 PM #37Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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. resum each group and recompare the difference. gosh this is kind of confusing... i think i'll just do it and see what it comes out to :)
 02122009, 02:58 PM #38Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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 viseversa. 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.
 02122009, 03:35 PM #39The 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.
Java Code:G1: [[B]55, 13[/B], 3, 1, 1] G2: [[B]34, 21[/B], 8, 5, 2] SUMG1: 73 SUMG2: 70
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)= 13Last edited by angryboy; 02122009 at 03:50 PM.
USE CODE TAGS> [CODE]...[/CODE]
Get NotePad++ (free)
 02122009, 06:57 PM #40Member
 Join Date
 Jan 2009
 Posts
 40
 Rep Power
 0
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 7370=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..
Similar Threads

finding the largest k numbers in an array without sorting the whole list?
By jmmjm in forum Advanced JavaReplies: 5Last Post: 02072009, 08:48 AM 
printing two smallest numbers from a series of numbers
By trofyscarz in forum New To JavaReplies: 2Last Post: 10142008, 11:46 PM 
sorting
By jot321 in forum New To JavaReplies: 18Last Post: 10022008, 10:30 AM 
sorting problem
By mcal in forum New To JavaReplies: 1Last Post: 02142008, 09:13 AM 
sorting JTable
By mansi_3001 in forum Advanced JavaReplies: 3Last Post: 08102007, 06:29 PM
Bookmarks