[Tutor] Exhaustive Enumeration
jeremiah
jeremiah.jester at panasonic.aero
Mon Sep 22 18:34:54 CEST 2008
Download links...
1) Think Python (about 240 pages)--Allen Downey and
http://www.greenteapress.com/thinkpython/thinkpython.html
> 2) A Byte of Python (about 100 pages)
http://www.swaroopch.com/notes/Python#Download
On Sun, 2008-09-21 at 16:31 -0400, Robert Berman wrote:
> First, thank you for the explanation.
>
> I admire your desire to learn bull riding by jumping on the monster's
> back. The problem with assignments based on a course is that many
> professors and associates have learned the only way to insure student
> class attendance is to obfuscate the assignment list. I think you may
> be missing some important information available to anyone with the
> class syllabus or the notes of an above average student. It could
> also be that at this time this assignment might be more than you
> should tackle. You certainly know more about your own skill level than
> anyone else.
>
> The best possible suggestions I have to offer is to download two
> python tutorial texts (neither of which is quick to read or
> superficial in content).
>
> 1) Think Python (about 240 pages)--Allen Downey and
>
> 2) A Byte of Python (about 100 pages)
>
> I use a Byte of Python as a very good reference manual. Think Python
> has a number of problems after each chapter as well as some problems
> that will make your brain itch as you solve them. Think Python might
> be a very good way to get into the functionalities that might make
> your MIT teaser a bit more manageable.
>
> In any case, best of luck no matter which path you pursue.
>
> Robert
>
>
>
> btkuhn at email.unc.edu wrote:
> > I'm actually not enrolled in the course; MIT puts some of its course
> > materials available online as a general resource. I am out of school
> > and trying to teach myself python on my own. I'm very much a
> > beginner, and since I'm not privy to the lectures or notes from this
> > course I have to fill in things from other sources. Basically, with
> > respect to this problem, I'm at a loss as to how to approach it. My
> > first thought was to use some sort of nested for loop structure to
> > iterate through each possible state combination, but I don't think
> > this is possible, since a for loop would just test for, for
> > instance, (state 1 and 2, state 1 and 3, state 1 and 4, etc.) and
> > not (state 1 and 3, state 1 and 2 and 3, etc.). I could maybe make
> > it work for a very small number of states, but if you are taking 10
> > states as arguments I don't see a way this could work. Also, the way
> > the question is asked seems to imply that the new code will go after
> > the existing code, and also that it will be only about five lines.
> > I'm guessing that maybe some kind of recursion is required but I
> > really don't know, and recursion is a new concept to me as well.
> >
> > Thanks!
> >
> > Quoting Robert Berman <bermanrl at embarqmail.com>:
> >
> > > A very interesting problem. Given this is homework, I am
> > > not
> > > sure what it is you want.
> > >
> > > Do you want the solution coded and tested?
> > > Do you want this to include two or three algorithms optimized for
> > > speed as well as accuracy?
> > >
> > > I think the problem is well enough defined so that you do not
> > > need
> > > any clarification of what it is your professor wants from you.
> > >
> > > If you would like some help finding a solution set, perhaps you
> > > would consider submitting some of your own solutions and
> > > commentary
> > > as to where your ideas are breaking down. Then, probably, a number
> > > of
> > > people will jump in to help you.
> > >
> > > Robert
> > >
> > > btkuhn at email.unc.edu wrote: This is from the MIT Opencourseware
> > > intro
> > > to computer science course, which I've been working my way
> > > through. I
> > > understand what needs to be done (I think), which is basically to
> > > test each possibility and return the list of states with the most
> > > electoral votes that can be paid for under the campaign budget. I
> > > am
> > > just at a loss as to how to do it, and I've been thinking about
> > > it
> > > all weekend. Here is the problem I am referring to. One assumption
> > > is
> > > that every $1 of money spent in a state translates into a popular
> > > vote. Many thanks for any suggestions. Also, the next part of the
> > > question asks to do the same thing using "Branch and Bound", which
> > > I
> > > also anticipate having trouble with. If I haven't described
> > > things
> > > sufficiently, the complete problem is available at:
> > >
> > > http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2007/Assignments/index.htm
> > > , problem 5.
> > >
> > > Complete and test this function according to her specification
> > > below.
> > > Note that she was using exhaustive
> > > enumeration to compute the result. Your friend assured you that
> > > the
> > > function needs no more than 5 additional
> > > lines of code.
> > >
> > > # Problem 2: Exhaustive enumeration
> > > def finance_campaign_ee(budget, free_states): """
> > > Takes a budget, in dollars, and a list of available states, as
> > > a
> > > list of dictionaries.
> > >
> > > Computes and returns the list of states that maximizes the
> > > total
> > > number of electoral votes such that these states can be
> > > acquired
> > > on the budget. Returns an empty list if no states can be
> > > acquired.
> > >
> > > """
> > > cheap_states=[]
> > > for s in free_states:
> > > if s['pop'] <= budget:
> > > cheap_states.append(s)
> > >
> > > # Base case
> > > if len(cheap_states)==0:
> > > res_list=[]
> > > # Recursive case
> > > else:
> > > curr_state=cheap_states[0]
> > > other_states=cheap_states[1:]
> > >
> > > inc_states=finance_campaign_ee( budget-curr_state['pop'],
> > > other_states)
> > > inc_states.append(curr_state)
> > > inc_evotes=total_evotes(inc_states)
> > >
> > > excl_states=finance_campaign_ee( budget, other_states )
> > > excl_evotes=total_evotes(excl_states)
> > >
> > > # ... your code goes here ...
> > > res_list = return res_list
> > >
> > > _______________________________________________
> > > Tutor maillist - Tutor at python.org
> > > http://mail.python.org/mailman/listinfo/tutor
> > >
> > >
> >
> >
> > _______________________________________________
> > Tutor maillist - Tutor at python.org
> > http://mail.python.org/mailman/listinfo/tutor
> >
> _______________________________________________
> Tutor maillist - Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
Disclaimer: The information contained in this transmission, including any
attachments, may contain confidential information of Panasonic Avionics
Corporation. This transmission is intended only for the use of the
addressee(s) listed above. Unauthorized review, dissemination or other use
of the information contained in this transmission is strictly prohibited.
If you have received this transmission in error or have reason to believe
you are not authorized to receive it, please notify the sender by return
email and promptly delete the transmission.
More information about the Tutor
mailing list