Jeff wrote at Thu, 19 Sep 2002 01:27:27 +0200: >> But could it be, we missed the simplest, but acceptable algorithm: >> >> [snipped my algorithm for shortness] > > mmm - looks like a more complex approach to me?
Hrm, yep. I liked your algorithm as it is quick and easy. But on the other hand the results aren't as good as possible. Imagine some very unnormal number rows, e.g. the n^10 number or exp(n). It's important to group numbers as low as possible with the highest numbers. But you're right, the time complexity of my algorithm is only O(n^2) what is really slow. Using a binary search e.g. but will reduce the time complexity to O(n log(n)). In fact it's the same time complexity as your algorithm (as it has to sort n/3 elements). Of course, your algorithm is still a bit quicker :-) > The point of the first approach was to create approximate groups using > the smallest and largest values in a quick first pass. The bulk of the > work is easily performed. The second and final pass using the sorted > partial groups and the sorted remaining values will always associate the > best available value with the right partial group. > > I think this would also be easier to extend to groups of more than three > numbers - you just extend the initial approximation pass to group more > numbers from either end. It gets a little more interesting when the > desired number of elements in a group is even, as you cant just blindly > grab both ends. That's the same way for my proposed algorithm, also I wouldn't feel very nice with such a solution. But I'm afraid a good solution would be confrontated with subset-sum problems what is a hard problem (allthough there are some polynomial approximations). > Using a sort feels simpler than calculating a target average and > iterating through all remaining numbers to see which value will bring > the partial group closest to the desired target. Remember that @numbers > is already sorted. I would guess that the 'calc a target and search for > best fit' algorithm actually does more work as coded above, consider > that it creates one partial group, and then searches through all > remaining numbers for the best fit. It then creates a second partial > group, and searches through all remaining numbers for the best fit, etc > etc etc. ACK. Cheerio, Janek -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
