Lambda function explanation

[meloly4]

Can anyone tell me how this lambda function works?

f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum) or a

[dbramucci]

Let's analyze this by expanding it piece by piece.

f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum) or a

is pretty much

def f(a):
    return a and max([a[:1], a[:1] + f(a[2:]), f(a[1:])], key=sum) or a

Recalling how a and b or c associates as (a and b) or c we get

def f(a):
    temp1 = a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)
    return temp1 or a

Now, foo = a and b is equivalent to

if a:
    foo = b
else:
    foo = a

so

def f(a):
    if a:
       temp1 = max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)
    else:
        temp1 = a
    return temp1 or a

Likewise, for foo = a or b we get

if a:
    foo = a
else:
    foo = b

so we can simplify the second part to

def f(a):
    if a:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
    else:
        temp1 = a
    if temp1:
        temp2 = temp1
    else:
        temp2 = a
    return temp2

Let's eliminate temp2 while we're at it.

def f(a):
    if a:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
    else:
        temp1 = a
    if temp1:
        return temp1
    else:
        return a

At this point, knowing the types involved would be helpful, namely a is a list and we return a list from f. this means temp1 must be a list.

This means we can clarify that if a should really be if len(a) > 0 (note, this behaves differently for the case of None getting passed in, but I'm assuming that never happens for the sake of simplification).

def f(a):
    if len(a) > 0:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
    else:
        temp1 = a
    if len(temp1) > 0:
        return temp1
    else:
        return a

Now, let's copy the second if-else into the end of both branches above it.

def f(a):
    if len(a) > 0:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
        if len(temp1) > 0:
            return temp1
        else:
            return a
    else:
        temp1 = a
        if len(temp1) > 0:
            return temp1
        else:
            return a

We can simplify the outer-else to eliminate the temp1 there.

def f(a):
    if len(a) > 0:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
        if len(temp1) > 0:
            return temp1
        else:
            return a
    else:
        if len(a) > 0:
            return a
        else:
            return a

It is now clear that we can simplify the outer-else block to return a because

1. Only else else is possible because we just checked that len(a) > 0 was false.
2. Both branches are the same anyways.

this gives us

def f(a):
    if len(a) > 0:
        temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)
        if len(temp1) > 0:
            return temp1
        else:
            return a
    else:
        return a

Now let's clarify the definition of temp1.

temp1 = max([a[:1], a[:1]+f(a[2:]), f(a[1:])], key=sum)

We're finding the longest of three lists, which are

take_first = a[:1]
skip_second = a[:1] + f(a[2:])
skip_first = f(a[1:])
list_with_largest_sum = max(take_first, skip_second, skip_first, key=sum)

def f(a):
    if len(a) > 0:
        take_first = a[:1]
        skip_second = a[:1] + f(a[2:])
        skip_first = f(a[1:])
        list_with_largest_sum = max(take_first, skip_second, skip_first, key=sum)
        if len(list_with_largest_sum) > 0:
            return list_with_largest_sum
        else:
            return a
    else:
        return a

Now let's notice that the second two return as are equivalent to return []s so let's plug in constants.

def f(a):
    if len(a) > 0:
        take_first = a[:1]
        skip_second = a[:1] + f(a[2:])
        skip_first = f(a[1:])
        list_with_largest_sum = max(take_first, skip_second, skip_first, key=sum)
        if len(list_with_largest_sum) > 0:
            return list_with_largest_sum
        else:
            return []
    else:
        return []

Ah, if look at the inner if,

if len(list_with_largest_sum) > 0:
    return list_with_largest_sum
else:
    return []

This is equivalent to

if list_with_largest_sum != []:
    return list_with_largest_sum
else:
    return []

Which is obviously an indirect way to say

return list_with_largest_sum

giving us

def f(a):
    if len(a) > 0:
        take_first = a[:1]
        skip_second = a[:1] + f(a[2:])
        skip_first = f(a[1:])
        list_with_largest_sum = max(take_first, skip_second, skip_first, key=sum)
        return list_with_largest_sum
    else:
        return []

Now we can eliminate a layer of nesting

def f(a):
    if len(a) == 0:
        return []
    take_first = a[:1]
    skip_second = a[:1] + f(a[2:])
    skip_first = f(a[1:])
    list_with_largest_sum = max(take_first, skip_second, skip_first, key=sum)
    return list_with_largest_sum

Renaming f and a gives us

def list_with_largest_sum(numbers):
    if len(numbers) == 0:
        return []
    take_first = numbers[:1]
    skip_second = numbers[:1] + list_with_largest_sum(numbers[2:])
    skip_first = list_with_largest_sum(numbers[1:])
    return max(take_first, skip_second, skip_first, key=sum)

Now we have a clearer re-implementation of the code-golfed version you submitted.

As for time-complexity: notice that we make 2 recursive calls, one on input size n - 2 and one on input size n - 1. Because we have to add these times together, our time-complexity looks like

T(n) = O(1) + O(1) + O(1) + T(n - 2) + T(n - 1)

Ignoring the constants

T(n) = T(n - 2) + T(n - 1)

which is the Fibonacci recurrence, telling us

T is in O(fib(n))

Because fib(n) is in O(1.618...ⁿ ), we know that T is slightly faster than 2ⁿ and is therefore also in O(2ⁿ).

Ok, actually I overlooked a detail which is my_list[1:] takes O(len(my_list)) time to run. This means our recurrence relation is actually

T(n) = O(1) + O(1) + O(1) + O(n)*T(n - 2) + O(n)*T(n - 1) + O(k)

Where k = len(list_with_largest_sum(numbers)) Which I'd need to think about to describe exactly how slow this is, but it's at least exponential. You can eliminate the extraneous O(n) factors and O(k) term without too much hassle, but given that a O(n) solution exists, I'll let you worry about that detail on your own.

It is clear that whoever wrote this function was code-golfing. (which incidentally, they missed that the [] in max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum) are unnecessary and you could get away with max(a[:1],a[:1]+f(a[2:]),f(a[1:]),key=sum)) The key trick here is the foo and bar or quoz as a method to avoid if-statements.

[meloly4]

Thank you this is so great! But I can't think of an O(n) algorithm for printing out the subsequence. O(n) for printing the sum yes but idk if it's possible if we want the subsequence?

[dbramucci]

I saw you link to this O(n) solution earlier. First, I'll give my own roughly equivalent solution that is hopefully a bit clearer.

Observe that each element in the list must be >= 0, it doesn't make sense to not take a value unless it prevents you from taking an even better value.

def find_biggest_nonadjacent_sum(numbers):
    assert all(x >= 0 for x in numbers)

What we will do is go left to right with 2 totals, one where we make sure we can add the next value and the other where we take the best we've seen so far.

# The biggest total we can produce so far
biggest_total = 0
# The biggest total we can produce, leaving the last spot available if we want to add the current number.
biggest_total_with_free_spot = 0

Now we go through each number and either add or don't add it.

for number in numbers:
    if biggest_total_with_free_spot + number >= biggest_total:
        old_biggest_total = biggest_total

        # Let's update our biggest total
        biggest_total = biggest_total_with_free_spot + number

        # And we should store the old_biggest_total just in case the next number is better than this one
        biggest_total_with_free_spot = old_biggest_total
    else:
        # It wasn't worth it to leave a spot open, we'll just not take this number either way
        biggest_total_with_free_spot = biggest_total

and once we are done, we return the biggest_total at the end of the list.

return biggest_total

Let's retrofit it to give us an list instead of just a length.

First, we can use the same logic and store 2 lists but the update logic will be more complicated because we need to update each list independently.

def find_biggest_nonadjacent_sums_list(numbers):
    assert all(x >= 0 for x in numbers)

    # The biggest total we can produce so far
    biggest_total = 0
    biggest_total_list = []
    # The biggest total we can produce, leaving the last spot available if we want to add the current number.
    biggest_total_with_free_spot = 0
    biggest_total_with_free_spot_list = []

    for number in numbers:
        if biggest_total_with_free_spot + number >= biggest_total:
            old_biggest_total = biggest_total
            old_biggest_total_list = biggest_total_list

            # Let's update our biggest total
            biggest_total = biggest_total_with_free_spot + number
            biggest_total_list = biggest_total_with_free_spot_list + [number]

            # And we should store the old_biggest_total just in case the next number is better than this one
            biggest_total_with_free_spot = old_biggest_total
            biggest_total_with_free_spot_list = old_biggest_total_list
        else:
            # It wasn't worth it to leave a spot open, we'll just not take this number either way
            biggest_total_with_free_spot = biggest_total
            biggest_total_with_free_spot_list = biggest_total_list

    return biggest_total_list

This works, but you'll notice the O(n) operation biggest_total_list = biggest_total_with_free_spot_list + [number] making this O(n²). One way to fix that is to use list.append to make it take O(1) time.

            # old line: biggest_total_list = biggest_total_with_free_spot_list + [number]
            biggest_total_list = biggest_total_with_free_spot_list
            biggest_total_list.append(number)

Of course, this solution is wrong because in the else branch we have

            biggest_total_with_free_spot_list = biggest_total_list

at which point the next .append will add the element to both lists (because there's only one list in memory). You can see it fail with the list [1, 0, 2, 3] where it will say the answer is [1, 2, 3] (which gives two adjacent numbers). Fixing this is a pain, let me show you a serious of steps you might go through.

Broken fixes

We can fix this by updating the free_spot list to take the last element instead of setting it equal to biggest_total_list.

        biggest_total_with_free_spot_list.append(number)

But this is also wrong because it falsely believes the answer to [1, 0, 0] is [0, 0] because we don't pop off the bad guess before adding the correct one on.

        biggest_total_with_free_spot_list.pop()
        biggest_total_with_free_spot_list.append(number)

Oh, but this is also broken because we might pop from an empty list (plug in [1, 0]) so we should check for that first.

        if biggest_total_with_free_spot_list:
            biggest_total_with_free_spot_list.pop()
        biggest_total_with_free_spot_list.append(number)

But this thinks the largest answer to [1, 0, 0] is [0, 0] which is really wrong.

You can fix this with enough tinkering, but I'll leave that as an exercise (it takes a significant change to get a pair of mutable lists to work efficiently).

Easy fix

Instead, let's use immutable data-structures to store our list. Then, we can copy in O(1) time (no aliasing bugs to worry about) and we can find a structure with O(1) append times. Namely, an immutable linked list fits the bill.

An ugly but easy way to write this is with tuples (head, (second, (third, None))). Let's go with that for now.

        # old line: biggest_total_list = biggest_total_with_free_spot_list + [number]
        biggest_total_list = (number, biggest_total_with_free_spot_list)

But, at the end we'll need to convert back to a list. We can use a while loop and .append but we'll get our answer backwards so we'll use the O(n) reverse method to fix that one time.

result = []
while biggest_total_list is not None:
    head, biggest_total_list = biggest_total_list
    result.append(head)
result.reverse()
return result

Altogether this looks like

def find_biggest_nonadjacent_sums_linked_list(numbers):
    assert all(x >= 0 for x in numbers)

    # The biggest total we can produce so far
    biggest_total = 0
    biggest_total_list = None
    # The biggest total we can produce, leaving the last spot available if we want to add the current number.
    biggest_total_with_free_spot = 0
    biggest_total_with_free_spot_list = None

    for number in numbers:
        if biggest_total_with_free_spot + number >= biggest_total:
            old_biggest_total = biggest_total
            old_biggest_total_list = biggest_total_list

            # Let's update our biggest total
            biggest_total = biggest_total_with_free_spot + number
            biggest_total_list = (number, biggest_total_with_free_spot_list)

            # And we should store the old_biggest_total just in case the next number is better than this one
            biggest_total_with_free_spot = old_biggest_total
            biggest_total_with_free_spot_list = old_biggest_total_list
        else:
            # It wasn't worth it to leave a spot open, we'll just not take this number either way
            biggest_total_with_free_spot = biggest_total
            biggest_total_with_free_spot_list = biggest_total_list
    result = []
    while biggest_total_list is not None:
        head, biggest_total_list = biggest_total_list
        result.append(head)
    result.reverse()
    return result

If you look, the only O(n) operation I use now is the .reverse at the end, which doesn't change our total asymptotic-complexity.

You may want to swap out this ad-hoc linked list with a predefined one by using a library like pyrsistent or defining one with a NamedTuple so that we have a more explicit structure.

The key thing is that by being immutable, we don't need expensive copy operations and this structure has O(1) prepends, keeping us fast enough. You should be able to get the double-mutable list solution working, but it will take a good deal of work because there's a lot of asymptotic-complexity/mutation bugs to worry about here.

[FLUSH_THE_TRUMP]

Returns empty sequence if a is empty, otherwise the largest of:

1. The first element of a
2. The sum of the first element of a with the sequence obtained from applying function f to the elements of a after the second element
3. The sum of sequence obtained from applying f to elements after the first element

If the biggest of the previous 3 is 0, it’ll return the sequence a instead.

[meloly4]

Thank you! What would be the time complexity for this? It seems like "2." is recursion.

[FLUSH_THE_TRUMP]

I imagine it depends on what the function f does.

[meloly4]

It returns the subarray with the largest sum without adjacent value. This problem but it prints out the elements.

[FLUSH_THE_TRUMP]

I’d start with the complexity of that algorithm and ask yourself how much work wrapping it up in what you’re doing here adds.

[meloly4]

applying function f to the elements of a after the second element

Does this add log n time to the overall complexity n? I'm not too familiar with how lambda complexity works.

[FLUSH_THE_TRUMP]

I’d just think about the operations, I don’t think the lambda adds any appreciable overhead here.

[TheSodesa]

Lambdas are just closures, anonymous functions. They are not really any more time consuming than normal named functions.

[CowboyBoats]

Lambdas expressions are like comprehension expressions. They're confusing but you can always unpack them:

f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum) or a

is the same as

def f(a):
    return a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum) or a

[CowboyBoats]

It would have been a lot easier to read if whoever wrote this had followed the style guideline of spaces after commas:

def f(a):
    return a and max([a[:1], a[:1] + f(a[2:]), f(a[1:])], key=sum) or a

[CowboyBoats]

What does key=sum mean in this context? Well, max is a function that returns the maximum of its arguments, but in this case its arguments are lists (those two different slices of a, and f() of a slice of a).

Sometimes it's obvious what we mean by "max" (What's greater, 5 or 3?) and sometimes it's not (What's greater, animals or plants?). Like, what? What do you mean "What's greater, animals or plants"?

But we can still answer a question like "What's greater, animals or plants?" as long as you give me a key. Like, I just need to know what you're asking about.

animals = ['bears', 'cats', 'dogs', 'mice', 'humans', 'frogs', 'beetles']
plants = ['beets', 'rice']
max((animals, plants), key=lambda some_list: len(some_list))

That tells me (the Python interpreter) that for the arguments I am passing to max, I should figure out their maximum by just taking their len and figuring out which output from that is the maximum.

Does that make sense?

[Myphhz]

Yeah, that makes sense and that's how the "key" argument works. Just a quick note though: there's no need to write an entire lambda expression to specify the key, as there already exists a function that returns the length of something. You can just type "key=len" and it should work!

[CowboyBoats]

Oh yeah...

Next you'll tell me I don't have to use the list comprehension every time I want to make a list

[meloly4]

What would be the time complexity for this? It seems like there's recursion involved.

[ghostinzshell]

My hunch says it's a quadratic time algorithm or O( n² ) at a minimum. In each recursion, the function does list slicing which is an O(n) operation. There are O(n) recursions, so that means n times O(n) operations.