Strange behavior of python function

Question

I'm in a online course at edx of Python and I have to do this little program, I think that the function is right but it has the bug when a element is deleted from the List suddenly the next element is not consider into the test.

    def f(i):
       return i + 2
    def g(i):
       return i > 5


    def applyF_filterG(L, f, g):
        """
        Assumes L is a list of integers
        Assume functions f and g are defined for you. 
        f takes in an integer, applies a function, returns another integer 
        g takes in an integer, applies a Boolean function, 
        returns either True or False
        Mutates L such that, for each element i originally in L, L contains  
            i if g(f(i)) returns True, and no other elements
        Returns the largest element in the mutated L or -1 if the list is empty
        """
        # Your code here
        i = 0
        if len(L) == 0:
            return -1
        while i < len(L):
            if not g(f(L[i])):
                del L[i]
            i += 1
        return max(L)

If I try with this example L = [0, -10, 5, 6, -4, -2], the value of L should be L = [5,6] but the result is this [-10, 5, 6, -2] the element -10 is skipped when the 0 was deleted and the same happens with -4 and -2. Please help, I don't know how can solve this.

Long story short: you never want to mutate a list while iterating over it. — elethan, Oct 02 '16 at 02:30
If you do want to delete elements while iterating over a list (even though this generally isn't a good idea) the best way is to start with the largest index and work to the smallest. That way when an element is deleted, its deletion doesn't change any of the indices of the elements that you still need to visit. — John Coleman, Oct 02 '16 at 02:37

score 3 · Answer 1 · edited Jun 20 '20 at 09:12

The problem:

You're deleting elements from the list as you iterate over the list. Due to that, i no longer refers to the right element in the list.

To illustrate this problem, here's a sample run through your code.
_{For this example we are going to assume that the if statement deletes an element if it's value is even.}
_{I also assume that i has already been initialized.}

L = [1, 2, 6, 3, 4]

iteration 1

i == 0, L[i] == 1, we don't delete the element.
L == [1, 2, 6, 3, 4]

iteration 2

i == 1, L[i] == 2, element is deleted.
L == [1, 6, 3, 4]

iteration 3

i == 2, L[i] == 3, we don't delete the element.
L == [1, 6, 3, 4]
# Did you notice that we just skipped checking the 6 because its index moved?!

iteration 4

i == 3, L[i] == 4, element is deleted.
L == [1, 6, 3]

We're finished!

There's a couple of ways to do this. Although @Meerness already supplied one way to do it, here's another way you could do it just for completeness.

i = len(L) - 1
if i == -1:
    return -1

while i >= 0:
    if not g(f(L[i])):
        del L[i]
    i -= 1

How this works:

In this way of doing it, you count down from the topmost index. That way, the deletion of an element doesn't affect the indexes of elements that you still haven't checked.
_{My explanation of this way of doing it is a slightly reworded version of the comment by @JohnColeman.}
_{JSYK, though, I had already written this solution before I saw his comment so I didn't borrow the idea from him -- I only borrowed his explanation. :)}

Here's an example of what happens when we count down instead of counting up:

L = [1, 2, 6, 3, 4]

iteration 1

i == 4, L[i] == 4, element is deleted.
L == [1, 2, 6, 3]

iteration 2

i == 3, L[i] == 3, we don't delete the element.
L == [1, 2, 6, 3]

iteration 3

i == 2, L[i] == 6, element is deleted.
L == [1, 2, 3]

iteration 4

i == 1, L[i] == 2, element is deleted.
L == [1, 3]

iteration 5

i == 0, L[i] == 1, we don't delete the element.
L == [1, 3]

We're finished!

PS: Examples automatically generated with python3 script. :)

pat2013 · Accepted Answer · 2016-10-02T15:52:13.557

3

Try not to iterate through the list that you mutate inside the loop in Python. In this example, the index order changed after you delete the element. I created a copy of L before iterating it and it does the trick.

def applyF_filterG(L, f, g):
    copied_L = L[:]
    for i in copied_L:
        if not g(f(i)):
            L.remove(i)
    if len(L)==0:
        return -1
    else:
        return  max(L)

edited Oct 02 '16 at 15:52

answered Oct 02 '16 at 15:28

pat2013

46
3

This code works for any case, thank you. I noticed now what was my mistake. – DiegoLl0895 Oct 02 '16 at 19:04

score 2 · Answer 3 · answered Oct 02 '16 at 02:33

2

Mutating a list as you're iterating over it is a bad idea and will lead to unexpected behaviour. In general, you're better off creating a new list to work on.

In this specific case, your code can be fixed with an easy modification. Only iterate the index if you aren't deleting an element, so as not to skip ahead in the list.

while i < len(L):
    if not g(f(L[i])):
        del L[i]
    else:
        i += 1

answered Oct 02 '16 at 02:33

Blue Star

1,932
1
10
11

It solve my problem, thanks a lot. I noticed now what was my problem. – DiegoLl0895 Oct 02 '16 at 18:55

score 0 · Answer 4 · edited Oct 02 '16 at 06:12

def applyF_filterG(L, f, g):
    """
    Assumes L is a list of integers
    Assume functions f and g are defined for you. 
    f takes in an integer, applies a function, returns another integer 
    g takes in an integer, applies a Boolean function, 
        returns either True or False
    Mutates L such that, for each element i originally in L, L contains  
        i if g(f(i)) returns True, and no other elements
    Returns the largest element in the mutated L or -1 if the list is empty
    """

    M =[]
    for i in range(len(L)):
       if g(f(L[i])):
            M.append(L[i])
    L = M[:]
    if len(L)==0:
        return -1
    else:
        return max(L)

Strange behavior of python function

4 Answers4

iteration 1

iteration 2

iteration 3

iteration 4

We're finished!

iteration 1

iteration 2

iteration 3

iteration 4

iteration 5

We're finished!