Posts: 2
Threads: 1
Joined: Feb 2022
Can you help me with that please? I need to write a function max(L) which, for a given int-list L of length n≥1, returns the maximum length of an unimodular sequence.
(a sequence is called unimodular in case a0≤a1≤...≤ai≥ai+1≥...ad )
For example :
L=[1,2,3,2,1,3,6,3,6]
L contains two unimodular sequences : 1,2,3,2,1 of length 5 and 1,3,6,3 of length 4.
The first one has maximum length, therefore max(L) should return the value 5.
If you have any ideas from where i can start, share it with me!
thank you.
Posts: 6,221
Threads: 16
Joined: Feb 2020
This problem has a fairly obvious solution and probably a more subtle solution I haven't come up with yet. I don't know if there can be anything more optimized than the obvious solution because it finds the longest unimodular sequence in a sequence of size N in N steps.
Think of the list of numbers as a mountain range, each number representing altitude. You start at 1 and climb to 2, then further up you go from 2 to 3. The next step after 3 is 2, so you switch from ascending to descending. You descend from 3 to 2, then from 2 to 1. Your next step will have you start ascending again, so your descent is complete. You traversed the mountain. How many steps did it take?
If you have multiple mountains the process repeats. If you want to know the "longest" mountain you keep a record. The first mountain is the longest until you traverse a longer mountain, then it becomes the longest.
There are three tricky parts. You have to start with an ascent. If the sequence starts with numbers descending, how do you handle that? What do you do when you reach the end of the mountain range? Do you have a mountain without a descent? The final tricky part is what to do about valleys. If you sequence is [1,2,3,2,1,1,3,6,3,6], the two unimodular sequences are [1,2,3,2,1,1] and [1,1,3,6,3]. How do you count the flat valley as being part of two mountains?
Gribouillis and natalie like this post
Posts: 832
Threads: 131
Joined: Jul 2017
Since you have to increase then decrease, you need to go through the list checking each number against the next number, until the next number is lower. You have your high number.
Then you need carry on from 1 after your high number, looking for the next number that is higher than the previous number. Then you have lowest number and your sequence.
If the length of your sequence is longer than the length of the list which remains to be checked, then you know you have the longest sequence. You could add that check.
The minimum size of a sequence is 3, like: [1,2,1] so 3 plays a role here.
I was supposed to be doing something else, but I solved my PHP problem this morning, so I took a look at this. Interesting.
Finding the sequences is the problem. Finding the longest one is trivial after that.
This may give you some ideas, although, I haven't tried it on a randomly generated list. You may need to tweak!!
You could make a randomly generated list like this:
import random
mylist = []
length = 54 # or any number
for i in range(1, length):
num = random.randint(1, length)
mylist.append(num)mylist = [1,1,2,1,3,5,7,9,7,11,12,14,16,15,14,24,34,44,55,54,61,62,63,64,65,66,1,2,3]
def myApp(mylist):
# find the maximums
def getTempmax(go_up, alist):
for i in range(go_up, len(alist)-1):
num1 = alist[i]
num2 = alist[i+1]
print(num1, num2)
if num2 < num1:
print('temporary maximum is', num1)
tup = (i+1, num1)
print('tup_max is', tup)
return tup
# find the minimums
def getTempmin(go_down, alist):
if len(alist) - go_down < 3:
go_down = len(alist)
print('temporary minimum is', alist[-1])
return (go_down, alist[-1])
for j in range(go_down, len(alist)-1):
num3 = alist[j]
num4 = alist[j+1]
if num4 > num3:
print('temporary minimum is', num3)
tup = (j, num3)
print('tup_min is', tup)
return tup
# gotta start somewhere
def initialize(passlist):
print('This list is', len(passlist), 'long')
tup_max = getTempmax(0, passlist)
tup_min = getTempmin(tup_max[0], passlist)
alist = []
sequence = passlist[0:tup_min[0]+1]
alist.append(sequence)
print('First sequence is', sequence)
tup = (tup_max, tup_min, alist)
return tup
#mylist = [1,2,3,2,1,3,6,3,6,7,8,4,3,9,1,1,2,3,2,2,1,4,5,4,9,7,3,10,11]
start = initialize(mylist)
tup_max = start[0]
tup_min = start[1]
sequences = start[2]
while not len(mylist) - tup_min[0] <= 3:
count = tup_min[0]
tup_max = getTempmax(tup_min[0], mylist)
tup_min = getTempmin(tup_max[0], mylist)
sequence = mylist[count:tup_min[0]+1]
# the last sequence need special treatment
if sequence[-1] > sequence[-2]:
del sequence[-1]
print('sequence is', sequence)
sequences.append(sequence)
# now just loop through sequences to find the longest list
biggest_list = 0
for s in sequences:
longest_list = len(s)
if longest_list > biggest_list:
biggest_list = longest_list
print('最长的列出为：', biggest_list)
Posts: 4,500
Threads: 69
Joined: Jan 2018
Feb-10-2022, 08:34 AM
(This post was last modified: Feb-10-2022, 08:35 AM by Gribouillis.)
Following deanhystad's reply, the below function can help. It transforms the list into a string where 'a' means ascent, 'd' means descent and 'f' means flat. The result can be computed from the string.
>>> def _idiff(L):
... for a, b in zip(L, L[1:]):
... yield 'a' if a < b else ('f' if a == b else 'd')
...
>>> def idiff(L):
... return ''.join(_idiff(L))
...
>>> L = [1,2,3,2,1,1,3,6,3,6]
>>> idiff(L)
'aaddfaada'
>>>
Posts: 2
Threads: 1
Joined: Feb 2022
(Feb-10-2022, 07:29 AM)Pedroski55 Wrote: Since you have to increase then decrease, you need to go through the list checking each number against the next number, until the next number is lower. You have your high number.
Then you need carry on from 1 after your high number, looking for the next number that is higher than the previous number. Then you have lowest number and your sequence.
If the length of your sequence is longer than the length of the list which remains to be checked, then you know you have the longest sequence. You could add that check.
The minimum size of a sequence is 3, like: [1,2,1] so 3 plays a role here.
I was supposed to be doing something else, but I solved my PHP problem this morning, so I took a look at this. Interesting.
Finding the sequences is the problem. Finding the longest one is trivial after that.
This may give you some ideas, although, I haven't tried it on a randomly generated list. You may need to tweak!!
You could make a randomly generated list like this:
import random
mylist = []
length = 54 # or any number
for i in range(1, length):
num = random.randint(1, length)
mylist.append(num)mylist = [1,1,2,1,3,5,7,9,7,11,12,14,16,15,14,24,34,44,55,54,61,62,63,64,65,66,1,2,3]
def myApp(mylist):
# find the maximums
def getTempmax(go_up, alist):
for i in range(go_up, len(alist)-1):
num1 = alist[i]
num2 = alist[i+1]
print(num1, num2)
if num2 < num1:
print('temporary maximum is', num1)
tup = (i+1, num1)
print('tup_max is', tup)
return tup
# find the minimums
def getTempmin(go_down, alist):
if len(alist) - go_down < 3:
go_down = len(alist)
print('temporary minimum is', alist[-1])
return (go_down, alist[-1])
for j in range(go_down, len(alist)-1):
num3 = alist[j]
num4 = alist[j+1]
if num4 > num3:
print('temporary minimum is', num3)
tup = (j, num3)
print('tup_min is', tup)
return tup
# gotta start somewhere
def initialize(passlist):
print('This list is', len(passlist), 'long')
tup_max = getTempmax(0, passlist)
tup_min = getTempmin(tup_max[0], passlist)
alist = []
sequence = passlist[0:tup_min[0]+1]
alist.append(sequence)
print('First sequence is', sequence)
tup = (tup_max, tup_min, alist)
return tup
#mylist = [1,2,3,2,1,3,6,3,6,7,8,4,3,9,1,1,2,3,2,2,1,4,5,4,9,7,3,10,11]
start = initialize(mylist)
tup_max = start[0]
tup_min = start[1]
sequences = start[2]
while not len(mylist) - tup_min[0] <= 3:
count = tup_min[0]
tup_max = getTempmax(tup_min[0], mylist)
tup_min = getTempmin(tup_max[0], mylist)
sequence = mylist[count:tup_min[0]+1]
# the last sequence need special treatment
if sequence[-1] > sequence[-2]:
del sequence[-1]
print('sequence is', sequence)
sequences.append(sequence)
# now just loop through sequences to find the longest list
biggest_list = 0
for s in sequences:
longest_list = len(s)
if longest_list > biggest_list:
biggest_list = longest_list
print('最长的列出为：', biggest_list)
Thank you so much for your time and help!
I don't know if I understood it correctly, if the list L=[1,2,3,4,1,1,1] should normally return 7?
When I test it with your code, an error appears.
Posts: 832
Threads: 131
Joined: Jul 2017
Feb-12-2022, 07:54 AM
(This post was last modified: Feb-12-2022, 07:55 AM by Pedroski55.)
I'm happy if you got some ideas! Nice name, Natalie!
Maybe it's the Chinese! Change the Chinese for "The longest list is: "
I changed the last part to print each sequence:
# now just loop through sequences to find the longest list
biggest_list = 0
for s in sequences:
print('Sequence is', s)
longest_list = len(s)
if longest_list > biggest_list:
biggest_list = longest_list
print('最长的列出为：', biggest_list)One problem: I started with this list:
mylist = [12,1,2,3,1,2,3,4,5,6,7,6,1,2]
Then you get [12,1] as the first sequence. You can think of a way to avoid that!
I get this output in Idle:
Quote:Sequence is [12, 1]
最长的列出为： 2
Sequence is [1, 2, 3, 1]
最长的列出为： 4
Sequence is [1, 2, 3, 4, 5, 6, 7, 6, 1]
最长的列出为： 9
Make a random list for testing:
# generate a random list for testing
start = input('Enter a start number ... ')
stop = input('Enter a stop number ... ')
length = input('How long do you want your list? ')
mylist = [random.randint(int(start), int(stop)) for i in range(int(length) + 1)]
Posts: 6,221
Threads: 16
Joined: Feb 2020
Since we are doing homework now.
def unimod(seq):
"""
Return longest unimodal sequence in seq.
A sequence is unimodular when a0≤a1≤...≤ai≥ai+1≥...ad
"""
if len(seq) < 3: # No sequences < 3 are unimodular(?)
return []
ascending = None # We don't know if we are ascending or descending
_, start, end = longest = (0, 0, 0)
for p, n in zip(seq, seq[1:]):
if ascending is None:
# Have we found the first valley?
if n >= p:
ascending = True
start = end
elif ascending:
# Are we still ascending?
ascending = n >= p
elif n > p:
# Found start of next mountain. Was last mountain the longest?
ascending = True
longest = max(longest, (end-start+1, start, end+1))
# Back up to the start of the valley
start = end
while start > 0 and seq[start-1] == p:
start -= 1
end += 1
if ascending == False:
# Last sequence is unimodular. Is it longest?
longest = max(longest, (end-start+1, start, end+1))
_, start, end = longest
return seq[start:end]
# Test some sequences
assert(unimod([]) == [])
assert(unimod([1,2]) == [])
assert(unimod([2,1,2]) == [])
assert(unimod([5,4,3,2,1,2,3]) == [])
assert(unimod([1,2,1]) == [1,2,1])
assert(unimod([2,1,2,1,2]) == [1,2,1])
assert(unimod([5,4,3,2,1,2,1,2,3,4,5]) == [1,2,1])
assert(unimod([2,1,2,1,1,1,2,2,1]) == [1,1,1,2,2,1])
assert(unimod([1,2,3,2,1,2,3,3,2,1]) == [1,2,3,3,2,1])This is a one trick pony. I prefer writing more generic tools and using them to solve multiple problems. With a small modification unimod becomes a unimodal sequence generator. I can still find the longest sequence using max(). And if I only want the length, len(max())
def unimod(seq):
"""
Generate unimodal sequences found in seq.
A sequence is unimodular when a0≤a1≤...≤ai≥ai+1≥...ad
"""
if len(seq) < 3: # No sequences < 3 are unimodular(?)
return []
ascending = None
start = end = 0
for p, n in zip(seq, seq[1:]):
if ascending is None:
# Have we found the first valley?
if n >= p:
ascending = True
start = end
elif ascending:
# Are we still ascending?
ascending = n >= p
elif n > p:
# Found start of next mountain. Was last mountain the longest?
ascending = True
yield(seq[start:end+1])
# Back up to the start of the valley
start = end
while start > 0 and seq[start-1] == p:
start -= 1
end += 1
if ascending == False:
# Last sequence is unimodular. Is it longest?
yield(seq[start, end+1])
sequences = list(unimod([3,2,1,2,1,2,3,2,1,2,3,4,3,2,1,2,1,2,3]))
longest = max(sequences, key=len)
print("Unimodal sequences =", sequences)
print("Longest sequence =", longest, 'Length =', len(longest))Output: Unimodal sequences = [[1, 2, 1], [1, 2, 3, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 1]]
Longest sequence = [1, 2, 3, 4, 3, 2, 1] Length = 7
|
