CODEWITHSUNDEEP
pythonarraysrecursion
Heyya
Heyya

Reputation: 193

Cannot remove item from nested list using recursion in Python

As the title states. I am trying to iterate through a list using recursion and remove any number in the list (including nested lists) that is equal to a given number. Here is what I have so far:

def deepRemoveAll(e, L):
    if len(L) == 0:
        return L
    if type(L[0]) == type([]):
        return deepRemoveAll(e, L[0])
    if e == L[0]:
        L.pop(0)
        return deepRemoveAll(e, L)
    if e != L[0]:
        temp = L[0]
        L.pop(0)
        return [temp] + deepRemoveAll(e, L)

print(deepRemoveAll(47, [42, 47, [1, 2, [47, 48, 49], 50, 47, 51], 52]))

The code seems flawless to me but for some reason the function is returning the list [42, 1, 2, 48, 49]. This is incorrect because in this case, all I need to remove are any 47's contained within but it is also removing 50, 51, and 52. The nested lists also need to stay intact but this is combining everything into one and I cannot for the life of me figure out why.

Upvotes: 0

Views: 685

Answers (3)

DevLounge
DevLounge

Reputation: 8437

This should help:

def deep_remove_all(e, a_list):
    res = []
    for item in a_list:
        if isinstance(item, list):
            res.append(deep_remove_all(e, item))
        elif item != e:
            res.append(item)
    return res

You could also write it like this:

def deep_remove_all(e, a_list):
    res = []
    for item in a_list:
        if item == e:
            continue

        res.append( 
            deep_remove_all(e, item)
            if isinstance(item, list) 
            else item
        )

    return res

Upvotes: 3

aghast
aghast

Reputation: 15310

Let's look at your code and find some stuff to fix:

def deepRemoveAll(e, L):
    if len(L) == 0:
            return L;
    if type(L[0]) == type([]):
            return deepRemoveAll(e, L[0]);
    if e == L[0]:
            L.pop(0);
            return deepRemoveAll(e, L);
    if e != L[0]:
            temp = L[0];
            L.pop(0);
            return [temp] + deepRemoveAll(e, L);

print(deepRemoveAll(47, [42, 47, [1, 2, [47, 48, 49], 50, 47, 51], 52]));

The first thing I see is just a quibble: type([]). In modern Python, that's list.

But before we change that, I notice you're doing a lot with L[0], and you almost always pop it. Let's make that common:

def deepRemoveAll(e, L):
    if len(L) == 0: return L

    l0 = L.pop(0)

Now we've got l0 (so not more repeated indexing) and it's out. We can put it back, or not, as we decide.

if type(l0) == list:

That will fix the type([]) above. But what do we do if the first element is a sublist? Obviously, we replace the first element with a deep-cleaned version of the first element:

if type(l0) == list:
    l0 = deepRemoveAll(e, l0)

It's still going to be the first element, but now we know it's clean.

Your next steps are to check if l0 is the e we want to remove. If so, you don't replace the start of the list - you just return cleaned-up remainder. That's correct, and it's also mutually exclusive with being a sub-list, so we can use an else or elif:

elif l0 == e:
    return deepRemoveAll(e, L)

And finally, there's the case where l0 != e. In this case, we want to clean the rest of L, and stick the l0 value back at the front.

But wait! That's also what we want to do in the case where l0 was a list, remember? All we did so far is clean up l0.

So let's fall out of the if/elif, so that we can merge the top code (l0 is a list) with the else code that we haven't put in: l0 != e.

return [l0] + deepRemoveAll(e, L)

Wrap it all up:

def deepRemoveAll(e, L):
    if len(L) == 0: return L

    l0 = L.pop(0)

    if type(l0) == list:
        l0 = deepRemoveAll(e, l0)
    elif l0 == e:
        return deepRemoveAll(e, L)

    return [l0] + deepRemoveAll(e, L)

Upvotes: 0

Christopher Shroba
Christopher Shroba

Reputation: 7574

Look at these two lines:

if type(L[0]) == type([]):
    return deepRemoveAll(e, L[0]);

What you are saying here is:

If the first element of the list is a list, then recurse on that list and throw away the rest of the elements of this list.

For example, if you had L=[[1,2],3], your if type(L[0]) == type([]) check would return true, and you would say deepRemoveAll(e, [1,2]), and the 3 is gone, regardless of what e is.

To fix your code:

Simply change return deepRemoveAll(e, L[0]); to L[0] = deepRemoveAll(e, L[0]), so that the first element of the list gets turned into itself with all the 47's removed, and then continue on with the rest of the logic.

Upvotes: 2

Related Questions