425,805 Members | 1,100 Online Need help? Post your question and get tips & solutions from a community of 425,805 IT Pros & Developers. It's quick & easy.

# min max of a list

 P: n/a If this is the list. values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] as we can see there are peaks in the list.that is 0,72,0 is a group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak 9 and 0, 42, 26, 0 with 42 and so on... what I want is the left and right bound index of each bin(triangle).The list could as big as possible.So some heurestic algorithm which could first find max in the list and look for local maxima and minima and group its adjcent bounds.Then find next max and group the bins and so on. so that we can get [[0,2],[2,7],[7,10],[10,13]] ( indexes of the bounds in the values list). so first group [0,2] correspond to 0,72,0 in the values list and so on... Hope I am clear. Jul 19 '05 #1
13 Replies

 P: n/a qu*****@gmail.com wrote: If this is the list. values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] as we can see there are peaks in the list.that is 0,72,0 is a group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak 9 and 0, 42, 26, 0 with 42 and so on... what I want is the left and right bound index of each bin(triangle).The list could as big as possible.So some heurestic algorithm which could first find max in the list and look for local maxima and minima and group its adjcent bounds.Then find next max and group the bins and so on. so that we can get [[0,2],[2,7],[7,10],[10,13]] ( indexes of the bounds in the values list). so first group [0,2] correspond to 0,72,0 in the values list and so on... Hope I am clear. Not exactly your output, but hopefully you can tailor it to your needs: py> values = [0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] py> def isnonzero((index, val)): .... return val != 0 .... py> import itertools py> for nonzero, vals in itertools.groupby(enumerate(values), isnonzero): .... if nonzero: .... vals = list(vals) .... start = vals - 1 .... end = vals[-1] + 1 .... print [start, end], "values: ", values[start:end+1] .... [0, 2] values: [0, 72, 0] [2, 6] values: [0, 4, 9, 2, 0] [7, 10] values: [0, 42, 26, 0] [10, 13] values: [0, 282, 23, 0] [13, 15] values: [0, 101, 0] Note that the real work is done by itertools.groupby. Zero terms are grouped together and ignored; non-zero terms are gathered together in lists. STeVe Jul 19 '05 #2

 P: n/a Thanks for that. My version of python does'nt find "groupby". I am using python 2.3.2. Is there a way I could do it with out using groupby Jul 19 '05 #3

 P: n/a qu*****@gmail.com wrote: Thanks for that. My version of python does'nt find "groupby". I am using python 2.3.2. Is there a way I could do it with out using groupby itertools.groupby is in Python 2.4. The docs give a Python equivalent, so if for some reason you can't upgrade to the current version of Python, you can just copy the groupby code from there. STeVe http://docs.python.org/lib/itertools-functions.html#l2h-1379 Jul 19 '05 #4

 P: n/a what if we do something like this. Assume the values list is the content of a histogram. Then we see that values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] 1 is repeated 72 times, 3 -> 4 times and so on. That is the index would be the value repeated as many times as in the list. Now If we find the max and look for the adjcent index. FOr example take 282 : Index of 282 --> 11 now check for value of index 10 and 12 .If value(10) < value(9) then there is a dip as value(9) and value(11) are greater than value(10). that could be the lower bound of that range. then if value(11) and value(13) for value(12). if value(11)< value(10) there is a dip. SO the bounds of [10,12] -> [0,282,23] rather than [10, 13] values: [0, 282, 23, 0] ( in your case). How would this work. Is there someway I could do this faster. Jul 19 '05 #5

 P: n/a Hi Steve! I am not sure if I was clear with my previous post .Ok let me rephrase it . Assume the values list is the content of a histogram. Then we see that values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] 1 is repeated 72 times, 3 -> 4 times and so on. That is the index would be the value repeated as many times as in the list. Now If we find the max and look for the adjcent index. That is if we plot the above list as a histogram. We will have crests and troughs ie peaks and dips. if we find two dips then the region between the two dips could be a range like [0, 72, 2] .So here we are not looking for a zero. But if we find dips then we consider the regions between it as a bin and group it. | /\ | /\ / \ /\ | / \/ \/ \ |/_____________________________________ |----|-----|---| 1 2 3 so pictorially. In the above plot. If y axis is the list above. then we need to bin it this way. If I use you previous approach using the groupby then all these three regions will be considered as one. Hope I am clear this time. Jul 19 '05 #6

 P: n/a qu*****@gmail.com wrote: If this is the list. values = [ 0, 72, 0, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] as we can see there are peaks in the list.that is 0,72,0 is a group(triangle) with peak 72.then 0, 4, 9, 2, 0, 0 with peak 9 and 0, 42, 26, 0 with 42 and so on... what I want is the left and right bound index of each bin(triangle).The list could as big as possible.So some heurestic algorithm which could first find max in the list and look for local maxima and minima and group its adjcent bounds.Then find next max and group the bins and so on. so that we can get [[0,2],[2,7],[7,10],[10,13]] ( indexes of the bounds in the values list). so first group [0,2] correspond to 0,72,0 in the values list and so on... Hope I am clear. ISTM you just have to look for the valleys - places where the values change from descending to ascending. Here is a simple-minded way to do it: def findPeaks(values): groups = [] startIx = 0 lastValue = values ascending = True for i, value in enumerate(values[1:]): if value <= lastValue: ascending = False else: if not ascending: # Switch from descending to ascending groups.append( [startIx, i] ) startIx = i ascending = True lastValue = value # Get the last group if any if i > startIx: groups.append( [startIx, i] ) return groups values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] print findPeaks(values) ## prints: [[0, 2], [2, 7], [7, 10], [10, 13], [13, 18]] Kent Jul 19 '05 #7

 P: n/a qu*****@gmail.com wrote: Hi Steve! I am not sure if I was clear with my previous post .Ok let me rephrase it . Assume the values list is the content of a histogram. Then we see that values = [ 0, 72, 2, 4, 9, 2, 0, 0, 42, 26, 0, 282, 23, 0, 101, 0, 0, 0, 0, 0] 1 is repeated 72 times, 3 -> 4 times and so on. That is the index would be the value repeated as many times as in the list. Now If we find the max and look for the adjcent index. That is if we plot the above list as a histogram. We will have crests and troughs ie peaks and dips. if we find two dips then the region between the two dips could be a range like [0, 72, 2] .So here we are not looking for a zero. But if we find dips then we consider the regions between it as a bin and group it. | /\ | /\ / \ /\ | / \/ \/ \ |/_____________________________________ |----|-----|---| 1 2 3 so pictorially. In the above plot. If y axis is the list above. then we need to bin it this way. If I use you previous approach using the groupby then all these three regions will be considered as one. Hope I am clear this time. So you want the peaks and valleys basically. Well, using itools.window from http://aspn.activestate.com/ASPN/Coo.../Recipe/299529, you could do something like: py> values = [0,72,2,4,9,2,0,0,42,26,0,282,23,0,101,0,0,0,0,0] py> peaks = [i .... for i, (v1, v2, v3) in enumerate(itools.window(values)) .... if v1 < v2 and v2 > v3] py> peaks [1, 4, 8, 11, 14] py> valleys = [i .... for i, (v1, v2, v3) in enumerate(itools.window(values)) .... if v1 >= v2 and v2 <= v3] py> valleys [2, 6, 7, 10, 13, 15, 16, 17, 18] py> [(min((abs(p - v), v) for v in valleys +  if v < p), .... p, .... min((abs(p - v), v) for v in valleys if v > p)) .... for p in peaks] [(0, 1, 2), (2, 4, 6), (7, 8, 10), (10, 11, 13), (13, 14, 15)] This is not likely the most efficient approach, but it's pretty simple: * identify the peaks and valleys * identify the valley on each side of a peak STeVe Jul 19 '05 #8

 P: n/a Hi Kent, Thanks for that. But We are considering [..., 0, 101, 0, 0, 0, 0, 0] -> [13,18] .In fact if you look at the list, the histogram ends at 15 that is [0,101,0] --> [13,15]. Dont you think so. Jul 19 '05 #9

 P: n/a qu*****@gmail.com wrote: Hi Kent, Thanks for that. But We are considering [..., 0, 101, 0, 0, 0, 0, 0] -> [13,18] .In fact if you look at the list, the histogram ends at 15 that is [0,101,0] --> [13,15]. Dont you think so. Well you consider ..., 0, 4, 9, 2, 0, 0, ... as an interval [2, 7] in your example. How is that different from ..., 0, 101, 0, 0, 0, 0, 0 ? Kent Jul 19 '05 #10

 P: n/a I get a syntax error in : py> [(min((abs(p - v), v) for v in valleys +  if v < p), .... p, .... min((abs(p - v), v) for v in valleys if v > p)) .... for p in peaks] Jul 19 '05 #11

 P: n/a oh yes its the same case. even [0,4,9,2,0] as a set [2,6] and may be not [2,7]. Its not that you are wrong its jus that I was not clear. Sorry about that. Jul 19 '05 #12

 P: n/a qu*****@gmail.com wrote: I get a syntax error in : py> [(min((abs(p - v), v) for v in valleys +  if v < p), ... p, ... min((abs(p - v), v) for v in valleys if v > p)) ... for p in peaks] I think we already covered the part where you were using an older version of Python. In this case, the missing feature is "generator expressions" and they are inside the two min() calls. You might want to consider upgrading... -Peter Jul 19 '05 #13

 P: n/a Peter Hansen wrote: qu*****@gmail.com wrote: I get a syntax error in : py> [(min((abs(p - v), v) for v in valleys +  if v < p), ... p, ... min((abs(p - v), v) for v in valleys if v > p)) ... for p in peaks] I think we already covered the part where you were using an older version of Python. In this case, the missing feature is "generator expressions" and they are inside the two min() calls. You might want to consider upgrading... But if you can't, you should write this as something like: [(min([(abs(p - v), v) for v in valleys +  if v < p]), p, min([(abs(p - v), v) for v in valleys if v > p])) for p in peaks] Note the extra brackets in the min calls. STeVe Jul 19 '05 #14

### This discussion thread is closed

Replies have been disabled for this discussion. 