Training, Open Source computer languages
PerlPHPPythonMySQLApache / TomcatTclRubyJavaC and C++LinuxCSS 
Search for:
Home Accessibility Courses Diary The Mouth Forum Resources Site Map About Us Contact
doubt in python program

Posted by python_myfav (python_myfav), 25 March 2005
hi all,

i have a small problem for all those of you who love python programming...
it goes like this .......
the user gives some n nos. as input ......
then we need to divide them in to two groups such that the difference
between the sum of  square roots of the nos in each group is the least
using minimum cpu
time......
for better understanding here is an example..........
suppose i have 10 nos....
1,2....10
then i need to partition sqrt(1),sqrt(2)......sqrt(10) in to two groups
such that their sum is almost same or the difference is the least......

Posted by admin (Graham Ellis), 25 March 2005
That looks a bit like a "brainteaser" or perhaps a coursework assigment?   Or do you have a real life application?

You talk about efficiency.   I would tend to use map to create a tuple of all the square roots, sum the tuple and halve the sum to work out the target figure.

Take half of the square roots, add then up and see how far out you are. Add in and take out other numbers to get closer to the target and keep going until you can't improve the result.   It's a little bit like a linear programming problem.

There's no guarantee that you'll get the closest value this way, but you'll get pretty near.  If you're not satisfied with the answers, you can easily enough re-run the code taking a different (random) selection of the square roots as your iterative start point;  I've done something similar before and people are usually impressed by the speed and closeness achieved  

If you have problems with coding the algorithm, please do follow up with bits of code or specific questions and I'll write a bit further.   But is this IS a test question, you wouldn't want me give you the whole answer, would you  

Posted by python_myfav (python_myfav), 26 March 2005
hi,
u better give me the whole code .i have found some challenging ques in python in some site.i did not get some of them so i prefer having the whole code..  
bye



Posted by admin (Graham Ellis), 26 March 2005
Quote:
u better give me the whole code


I have to "draw the line" at providing complete answers that are more than just a few lines of code here.  I simply haven't got the time to do it, and if you're looking for something that's an answer to a coursework assignment (which I suspect here), then you won't learn anything if I do the whole thing for you.

We do, though, have an example of the type of iteration algorithm I've described on our web site at http://www.wellho.net/resources/ex.php4?item=p772/place_people ... and you're very welcome to read the code there and learn from it;  it's in Perl, but it's well commented / documented and should give you some excellent help.



This page is a thread posted to the opentalk forum at www.opentalk.org.uk and archived here for reference. To jump to the archive index please follow this link.

You can Add a comment or ranking to this page

© WELL HOUSE CONSULTANTS LTD., 2014: Well House Manor • 48 Spa Road • Melksham, Wiltshire • United Kingdom • SN12 7NY
PH: 01144 1225 708225 • FAX: 01144 1225 899360 • EMAIL: info@wellho.net • WEB: http://www.wellho.net • SKYPE: wellho