Assume I have the following list x = [1,2,3,3,2,0] and I'd like to count the number of monotonic items (increasing, decreasing and constant). So, in my example:
1. Increasing: [1,2], [2,3], [1,2,3]
2. Constant: [3,3]
3. Decreasing: [3,2], [2,0], [3,2,0]
Total of 7 items.
Thank you in advance.
Since you show no code, I'll just give you some hints. The main idea is to step through your sequence, starting with the second item (index 1), and update information for each item, counting the number of monotonic sequences that end at that item.
Store several pieces of information as you step through the list. First you need a counter for the three kinds of monotonic sequences. There is no need to count the kinds of sequences separately: you can count them all together in one counter. You need a three-way or four-way signal to note the kind of sequence (increasing, constant, or decreasing) for the previous monotone sequence, and you need an integer to show how long that previous monotonic sequence is. With that information you can update the appropriate counters with the appropriate amounts. Note that you need to be careful in handling the start of the list, before there are any monotonic sequences of any kind.
Now step through your input list, starting with the second item (index 1). Compare the current item with the previous item. Update the length of the current monotone sequence: if the direction of the last two items agrees with the previous direction then your monotone sequence has become one item larger; otherwise, you have a new monotone sequence with smallest length. Now increase your overall counter with the number of new monotone sequences. If your new sequence has length 2 (the previous and current items) you add 1, if the new sequence has length 3 you add 2, and so on.
Work on those hints. If you need more help, show more of your work and explain just where you are stuck, then ask for more help. But you need to show more of your own effort. I have written code that follows those hints, and it is nice, efficient, and short. Happy coding!
On the basis of another answerer, who believes that you have shown enough work, here is my code. (I show this code for the sake of completness--please do not remove your "accept" from the other answer.) I include two small functions that could easily be inserted into the main routine, but these are useful functions on their own.
def pairwise(seq):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
if seq:
return zip(seq, seq[1:])
else:
return zip()
def cmp(x, y):
"""Return an integer depending on the comparison of two values.
Return -1 if x < y,
0 if x == y,
1 if x > y.
"""
return (x > y) - (y > x) # a common Python trick: bool values to int
def count_monotonic_subsequences(seq):
"""Return the number of monotonic (consecutive) subsequences of
length at least 2 in a sequence."""
run_length = 0
prev_cmp = None # no comparisons done yet
count_so_far = 0
# For each item, add how many monotonic sequences end with that item
for prev_item, item in pairwise(seq):
this_cmp = cmp(prev_item, item)
if this_cmp == prev_cmp:
run_length += 1 # this item extends the previous mono subsequence
else:
run_length = 1 # this item begins a new monotonic subsequence
prev_cmp = this_cmp
count_so_far += run_length # add new mono subsequences ending here
return count_so_far
print(count_monotonic_subsequences([1,2,3,3,2,0])) # 7
It is much easier to tackle this problem by breaking it down into smaller steps. First, get the items grouped on their trend (increasing, equal or decreasing) by keeping track of previous and current values.
Gather all results and then break down the results into smaller lists as needed for the desired output in the second step.
I would encourage you to follow through the comments in code and try to implement the steps yourself.
x = [1,2,3,3,2,0]
prev = x[0]
curr = x[1] #keep track of two items together during iteration, previous and current
result = {"increasing": [],
"equal": [],
"decreasing": [],
}
def two_item_relation(prev, curr): #compare two items in list, results in what is effectively a 3 way flag
if prev < curr:
return "increasing"
elif prev == curr:
return "equal"
else:
return "decreasing"
prev_state = two_item_relation(prev, curr) #keep track of previous state
result[prev_state].append([prev]) #handle first item of list
x_shifted = iter(x)
next(x_shifted) #x_shifted is now similar to x[1:]
for curr in x_shifted:
curr_state = two_item_relation(prev, curr)
if prev_state == curr_state: #compare if current and previous states were same.
result[curr_state][-1].append(curr)
else: #states were different. aka a change in trend
result[curr_state].append([])
result[curr_state][-1].extend([prev, curr])
prev = curr
prev_state = curr_state
def all_subcombinations(lst): #given a list, get all "sublists" using sliding windows
if len(lst) < 3:
return [lst]
else:
result = []
for i in range(2, len(lst) + 1):
for j in range(len(lst) - i + 1):
result.extend([lst[j:j + i]])
return result
print(" all Outputs ")
result_all_combinations = {}
for k, v in result.items():
result_all_combinations[k] = []
for item in v:
result_all_combinations[k].extend(all_subcombinations(item))
print(result_all_combinations)
#Output:
{'increasing': [[1, 2], [2, 3], [1, 2, 3]],
'equal': [[3, 3]],
'decreasing': [[3, 2], [2, 0], [3, 2, 0]]}
