Could this be solve with list comprehension?

Hello,

This is my solution:

41

How can I turn it into a list comprehension? (Perhaps it is for some reason not possible? / requires some knowledge I don’t have as a beginner…)
Any tips would be very welcome, as I seem to be stuck.

A comprehension will result in a list, not a value. We want the function to return a value. The method you have used is effective enough. It goes through the list once, then exits with the maximum.

3 Likes

Thank you very much for the prompt and clear reply.

1 Like

For some silliness, that does employ a list comprehension…

a =  [95, 39, 76, 84, 19, 97, 26, 34]
while len(a) > 1:
    a = [x for x in a if x > a[0]]
print (a)    # [97]

This code is frought with flaws, which means it is unreliable. As a skeleton, it is useful, but only as a that. More logic is required.

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
    a = [x for x in a if x > a[0]] or [a[0]]
print (a)    # [98]

Test the above. It may have less flaws, but I’m not yet convinced it is letter perfect. Remove 19 from the first position, and run again. That was the flaw of the first version, which now seems repaired. We need more test scenarios to be sure that actually addresses the issue. Logically it is sound, to my mind, but we’re not standing on solid ground, as it were.

As complexity is concerned, we would be iterating a list which is getting progressively shorter each time, but it would still mean re-iteration, which would be a factor of more than 1 on N values in the original list. Since it is a constant, Big O would remain, O(N), but we can see it would still take more steps than once through the list.


Addendum

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
  u, v = a[0], a[1]    # symbolize as early as possible
  if v > u:
    a.pop(0)
  else:
    a.pop(1)
b =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(b) > 1:
  u, v = b[0], b[1]
  if v > u:
    b.remove(u)
  else:
    b.remove(v)
>>> a, b
([98], [98])
>>> 

Further Addendum

a =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(a) > 1:
  u, v = a[0], a[1]
  a.pop(0 if v > u else 1)

b =  [19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98]
while len(b) > 1:
  u, v = b[0], b[1]
  b.remove(u if v > u else v)

def max(sample):
  s = sample[:]
  while len(s) > 1:
    u, v = s[0], s[1]
    s.remove(u if v > u else v)
  return s[0]

Addendum: June 17 0400 UTC

This last function has everything we need, given we’ve called upon a built-in. It chomps down a list in N - 1 iterations. Safely an O(N) as complexity goes.

As we can see, there is no suggestion of equality. When two numbers are equal, the one is not greater than the other so is removed. One cannot think how to tinker with this code any further.

def min(sample):
  s = sample[:]
  while len(s) > 1:
    u, v = s[0], s[1]
    s.remove(u if v < u else v)
  return s[0]

But using no methods at all we get to the bottom very quickly…

def maximum(sample):
  s = sample[0]
  for x in sample:
    s = x if x > s else s
  return s
# maximum([19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98])
# 98
def minimum(sample):
  s = sample[0]
  for x in sample:
    s = x if x < s else s
  return s
# minimum([19, 98, 95, 39, 76, 84, 19, 97, 26, 34, 98])
# 19

Still O(N) but much faster, I would conclude. Time it with large lists and see how the two compare.

Bottom line, list comprehensions don’t really fit this type of problem. Comprehension and reduction are one way to see the picture. Brute force is the other. MIN and MAX seem to fit the brute force template.

This worked for me, but I feel like there might be a better solution. Probably could use a few more safeties.

def max_num(nums):
  maximum = [nums[i] for i in range(0,len(nums)) if (i == 0) or (nums[i-1] < nums[i])]
  return maximum[-1]

Update:

def max_num(nums):
  return [nums[i] for i in range(0,len(nums)) if (i == 0) or (nums[i-1] < nums[i])][-1]

Comparing adjacent numbers isn’t enough, consider [100,0,1]
1 is greater than 0, but it isn’t the maximum

Yep, account for. My code adds the first regardless and starts comparing from there. It is only adding if greater than the previous.

Your code does not account for that. It will return 1 for that list

I’ll check again when I have time, but it definietly worked for the activity and it should account for that with the first side of the or statement. It will add the 100 from the list and continue from there.

It’ll compare num[1] num[2]
num[2] is larger and gets included
You’re looking at the wrong list, the one you meant to look at doesn’t exist yet, you’re still creating it.

You can have some tests which do pass without it being overall correct.
A broken clock tells the right time twice a day.

So first off my code mostly works. as I mentioned I could use a few more safeties and I didn’t thoroughly check out all conditions. My code does work in a majority of cases except when the highest number is the first in the list. It works in all other cases I’ thrown at it so far. It is also clear from your early responses you did not understand what I was doing until later. My code does work in a majority of cases and I might ponder how to fix the ONE case you found that it doesn’t work in. Good job on finding a bug on mostly working code. My clock is correct except twice a day it seems. I will look into a patch.

Revised code that fixes the first item bug.

def max_num(nums):
  maximum = [nums[i] for i in range(0,len(nums)) if (nums[i-1] < nums[i])]
  return maximum[-1]

Update:

def max_num(nums):
  return [nums[i] for i in range(0,len(nums)) if (nums[i-1] < nums[i])][-1]

If you create lists with values picked between 1 and 1000 with a random length between 2 and 100 then your code will produce the wrong answer for most of those.

Another example where it returns 1:
[100,100,100,100,100,100,100,100,0,1]

The problem isn’t with the first element. The problem is that your code only considers the last two values, if the maximum is not found among the last two values, then the wrong result is produced.

The updated version still answers with 1

how about?
def max_num(nums):
nums.sort()
return nums[-1]

It’s important to do as little to disrupt our data structure as possible, namely preserve the original order. Once we sort we can never be sure to restore it.

There is a way to use sorting without affecting the original, sort a copy.

nums_sort = sorted(nums)
return nums_sort[-1]

The main problem though is that sorting is of higher abstraction level than max, should probably implement max in terms of things that are simpler than itself rather than something that does the whole task and more.

So for example part of max is iteration. PART - it’s a subproblem, doesn’t eclipse it.

An appropriate iteration pattern to use is reduce (combine values into an accumulated value using a specified action between the accumulator and each value to be combined into it)

the combining action would be max for two values, which is simpler than max for many values, again, a small part

def max_of_2(a, b):
    if a >= b:
        return a
    return b

def max_num(nums):
    return reduce(max_of_2, nums)

Don’t necessarily need to use function statements for it, since it’s combining functions, it could as well be an expression:

max_num = partial(reduce, lambda a, b: a if a >= b else b)
1 Like

Hi there! I am learning loop at the moment and having trouble with understanding the code below:
def max_num(nums):
maximum=nums[0]
for number in nums:
if number>maximum:
maximum=number

Could someone help me to understand how this loop works to find maximum number? Thank you very much.

return maxium

This initializes the variable to the first value in the list.

Iterate over the list

Replace the value with current number. Maximum is growing in value.

At the end of iteration, maximum will be the greatest value found in the list. There may be duplicates, but this method won’t be able to tell us that.

1 Like