CODEWITHSUNDEEP
pythonlistpython-2.7
Varuna Singh
Varuna Singh

Reputation: 78

Remove occuring elements from multiple lists (shorten multiple lists) by value

Say I have a list of lists:

[[0,0,0,1,2,3],[0,0,0,4,5,6],[0,0,0,0,7,8],[0,0,0,0,0,9]]

I want to end up with a list that would have removed common null/zero/keyword from each lists within that list to yield an output desired:

[[1,2,3],[4,5,6],[0,7,8],[0,0,9]]

Obviously, looping through every list within that list and then comparing it against all the other lists is beyond an ideal answer. Thanks.

Upvotes: 1

Views: 70

Answers (2)

roippi
roippi

Reputation: 25974

If you were to sort those sublists, you would find that the maximum one would have the number of zeroes you need to drop from all of them. So just find the max:

x = [[0,0,0,1,2,3],[0,0,0,4,5,6],[0,0,0,0,7,8],[0,0,0,0,0,9]]

max(x)
Out[2]: [0, 0, 0, 4, 5, 6]

figure out how many leading zeroes you need to drop:

from itertools import takewhile

#needlessly pedantic way of doing this
num_zeroes = len(list(takewhile(lambda p: p == 0, max(x))))

and slice accordingly:

[li[num_zeroes:] for li in x]
Out[12]: [[1, 2, 3], [4, 5, 6], [0, 7, 8], [0, 0, 9]]

Upvotes: 2

abarnert
abarnert

Reputation: 366213

Obviously, looping through every list within that list and then comparing it against all the other lists is beyond an ideal answer.

Well, there's really no way around comparing the prefix to the prefix of every list.

But you can avoid comparing each entire list to every list. In other words, you can make this O(NM), where M is the length of the common prefix, instead of O(N**2). Just do it in two passes, keeping track of the longest prefix seen so far during the first pass, then using the result in the second pass.

Alternatively, we can make it more explicit, calculating the nonzero prefix for each list with a max value. It should be obvious that this is the same number of steps (although it will be slower by a small constant, because it does the inner loop in Python instead of in C):

def first_nonzero(seq, stop=None):
    for i, val in enumerate(seq):
        if val or i == stop:
            return i
    return i

prefix = None
for lst in list_o_lists:
    prefix = first_nonzero(lst, prefix)

output = [lst[prefix:] for lst in list_o_lists]

Upvotes: 1

Related Questions