Re: [Tutor] array and dictionary
"Dinesh B Vadhia" <[EMAIL PROTECTED]> wrote
Hi! Say, I've got a numpy array/matrix of the form:
[[1 6 1 2 3]
[4 5 4 7 0]...
[2 1 0 5 6]]
I want to create a dictionary of rows (as the keys) mapped
to lists of non-zero numbers in that row
Caveat, I dont know about numpy arrays.But assuming they
act like Python lists
You can get the non zeros with a comprehension
nz = [n for n in row if n != 0]
you can get the row and index using enumerate
for n,r in enumerate(arr):
So to create a dictionary, combine the elements somethng like:
d ={}
for n,r in enumerate(arr):
d[n] = [v for v in r if v !=0]
I'm sure you could do it all in one line if you really wanted to!
Also the new any() function might be usable too.
All untested
HTH,
--
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] array and dictionary
Alan
Thanks but I've been a bit daft and described the wrong problem which is easy
to solve the long way. Starting again ...
Given a (numpy) array how do you create a dictionary of lists where the list
contains the column indexes of non-zero elements and the dictionary key is the
row index. The easy way is 2 for loops ie.
import numpy
from collections import defaultdict
A =
[[1 6 1 2 3]
[4 5 4 7 0]
[2 0 8 0 2]
[0 0 0 3 7]]
dict = defaultdict(list)
I = A.shape[0]
J = A.shape[1]
for i in xrange(0, I, 1):
for j in xrange(0, J, 1):
if a[i,j] > 0:
dict[i].append(j)
I want to find a faster/efficient way to do this without using the 2 for loops.
Thanks!
Btw, I posted this on the numpy list too to make sure that there aren't any
numpy functions that would help.
Dinesh
Message: 5
Date: Sun, 21 Sep 2008 09:15:00 +0100
From: "Alan Gauld" <[EMAIL PROTECTED]>
Subject: Re: [Tutor] array and dictionary
To: tutor@python.org
Message-ID: <[EMAIL PROTECTED]>
Content-Type: text/plain; format=flowed; charset="iso-8859-1";
reply-type=original
"Dinesh B Vadhia" <[EMAIL PROTECTED]> wrote
> Hi! Say, I've got a numpy array/matrix of the form:
>
> [[1 6 1 2 3]
> [4 5 4 7 0]...
> [2 1 0 5 6]]
>
> I want to create a dictionary of rows (as the keys) mapped
> to lists of non-zero numbers in that row
Caveat, I dont know about numpy arrays.But assuming they
act like Python lists
You can get the non zeros with a comprehension
nz = [n for n in row if n != 0]
you can get the row and index using enumerate
for n,r in enumerate(arr):
So to create a dictionary, combine the elements somethng like:
d ={}
for n,r in enumerate(arr):
d[n] = [v for v in r if v !=0]
I'm sure you could do it all in one line if you really wanted to!
Also the new any() function might be usable too.
All untested
HTH,
--
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
[Tutor] Exhaustive Enumeration
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@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Exhaustive Enumeration
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 [EMAIL PROTECTED] 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@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Exhaustive Enumeration
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 <[EMAIL PROTECTED]>: 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 [EMAIL PROTECTED] 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@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Exhaustive Enumeration
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 [EMAIL PROTECTED] 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 <[EMAIL PROTECTED]>: 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 [EMAIL PROTECTED] 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
Re: [Tutor] Exhaustive Enumeration
That it is. Jaggo wrote: Lol. And here I said to myself only, "What a nice challenge". On Sun, Sep 21, 2008 at 10:28 PM, Robert Berman <[EMAIL PROTECTED]> wrote: 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 [EMAIL PROTECTED] 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@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] array and dictionary
On Sun, Sep 21, 2008 at 2:17 PM, Dinesh B Vadhia
<[EMAIL PROTECTED]> wrote:
> Given a (numpy) array how do you create a dictionary of lists where the list
> contains the column indexes of non-zero elements and the dictionary key is
> the row index. The easy way is 2 for loops ie.
>
> import numpy
> from collections import defaultdict
> A =
> [[1 6 1 2 3]
> [4 5 4 7 0]
> [2 0 8 0 2]
> [0 0 0 3 7]]
>
> dict = defaultdict(list)
Don't use names of builtins as variable names!
> I = A.shape[0]
> J = A.shape[1]
> for i in xrange(0, I, 1):
> for j in xrange(0, J, 1):
> if a[i,j] > 0:
> dict[i].append(j)
>
> I want to find a faster/efficient way to do this without using the 2 for
> loops. Thanks!
Not sure about faster but this could be done with list/generator comprehensions:
In [37]: A = \
: [[1, 6, 1, 2, 3],
: [4, 5, 4, 7, 0],
: [2, 0, 8, 0, 2],
: [0, 0, 0, 3, 7]]
In [38]: d = dict( (i, [j for j, val in enumerate(row) if val > 0])
for i, row in enumerate(A))
In [39]: d
Out[39]: {0: [0, 1, 2, 3, 4], 1: [0, 1, 2, 3], 2: [0, 2, 4], 3: [3, 4]}
Kent
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] __init__ arguments storage
Here is another writeup on __new__() and __init__(); http://www.voidspace.org.uk/python/weblog/arch_d7_2008_09_20.shtml#e1014 Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] a simple keyboard art,,, gone wrong!
Try to put a 'r' letter before the opening-quote: print \ r""" _ ___ ___ ___ _ / ___| / | / |/ || ___| | |/ /| |/ /| /| || |__ | | _/ __| | / / |__/ | || __| | |_| | / / | | / / | || |___ \_/ /_/ |_| /_/|_||_| _ _ __ ___ / _ \ | | / / | | | _ \ | | | | | | / / | |__ | |_| | | | | | | | / /| __|| _ / | |_| | | |/ / | | | | \ \ \_/ |___/ |__| |_| \_\ """ Python was trying to interpret the '\'. Cheers. [ rui ] ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Exhaustive Enumeration
Thanks for the link it's really useful :) On Mon, Sep 22, 2008 at 2:10 AM, Robert Berman <[EMAIL PROTECTED]>wrote: > That it is. > > Jaggo wrote: > > Lol. And here I said to myself only, "What a nice challenge". > > On Sun, Sep 21, 2008 at 10:28 PM, Robert Berman <[EMAIL PROTECTED]>wrote: > >> 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 >> >> [EMAIL PROTECTED] 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@python.org >> http://mail.python.org/mailman/listinfo/tutor >> >> >> ___ >> Tutor maillist - Tutor@python.org >> http://mail.python.org/mailman/listinfo/tutor >> >> > > ___ > Tutor maillist - Tutor@python.org > http://mail.python.org/mailman/listinfo/tutor > > -- Cheers, Vishwajeet http://www.singhvishwajeet.com ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
