python3, удаление “подсписка” из списка

#python #алгоритм #python_3x

Нужно удалить из списка в вхождения, да не просто по элементам, а прям множество.
Т.е. если есть список: [0, 1, 2, 3, 1, 5, 3, 7], и например, кортеж, который удаляемых
элементов (1, 5, 3), нужно, чтобы в итоге получился список [0, 1, 2, 3, 7]. Как можно
легче всего такое реализовать?
    

Ответы

Ответ 1

Я бы попробовал что-то вроде такого:
1) изменение списка на месте (чуть сложнее)

def is_equal(lst, pattern):
    if len(lst) != len(pattern):
        return False
    for a, b in zip(lst, pattern):
        if a != b:
            return False
    return True

def clear_list(lst, pattern):
    index = []
    l = len(pattern)
    rng = iter(xrange(len(lst)))
    while True:
        try:
            i = next(rng)
            if is_equal(lst[i:i+l], pattern):
                for j in range(i, i + l):
                    index.append(j)
                    if j != i + l - 1:
                        next(rng)

        except StopIteration:
            break
    index.reverse()
    for i in index:
        del lst[i]

l = [1, 2, 1, 2, 1, 1, 2, 1, 3, 4, 1]
p = (1, 2, 1)
clear_list(l, p)
print l # --> [2, 1, 3, 4, 1]


Оно даже работает.



2) для генерации нового списка (все проще):

def clear2(lst, pattern):
    res = []
    l = len(pattern)
    r = iter(xrange(len(lst)))
    while True:
        try:
            i = next(r)
            if is_equal(lst[i:i+l], pattern):
                for j in range(i, i + l - 1):
                    next(r)
            else:
                res.append(lst[i])
        except StopIteration:
            break
    return res

l = [1, 2, 1, 2, 1, 1, 2, 1, 3, 4, 1, 2]
p = (1, 2, 1)
print l
print clear2(l, p) # -> [2, 1, 3, 4, 1, 2]




Потестил на 5 примерах, оба варианта рабочии.


Ответ 2

Фактически условие эквивалентно удалению подстроки из строки:

>>> list(bytes([0, 1, 2, 3, 1, 5, 3, 7]).replace(bytes((1, 5, 3)), b''))
[0, 1, 2, 3, 7]


Вот простой «в лоб» O(n*m) алгоритм по удалению subseq подпоследовательности из lst
списка:

def removed(lst, subseq):
    subseq = type(lst)(subseq) # копируем, чтобы тот же тип был (для == ниже)
    i = 0
    while i < len(lst):
        if lst[i:i+len(subseq)] == subseq: # нашли подпоследовательность
            i += len(subseq) # пропускаем
        else:
            yield lst[i] # передаём как есть
            i += 1


Пример:

>>> list(removed([0, 1, 2, 3, 1, 5, 3, 7], (1, 5, 3)))
[0, 1, 2, 3, 7]


Можно заметно улучшить производительность (до O(n) вместо O(n*m)) в некоторых случаях,
с помощью алгоритмов, используемых для нахождения позиции подстроки в строке в Питоне
(Boyer-Moore + Horspool и Sunday).

Можно модифицировать алгоритм, чтобы принимать на вход произвольные итерируемые объекты,
а не только последовательности. Или чтобы изменять входной список по месту без создания
копии.


Ответ 3

Добавлю и свой пример :)

def find_sublist(l, m):
    for i in range(len(l)):
        try:
            if tuple(l[i: i + len(m)]) == tuple(m):
                yield i, i + len(m)
        except IndexError:
            pass

def delete_sublist(l, m):
    for i, j in find_sublist(l, m):
        del l[i: j]


Ответ 4

def is_equal(lst, pattern):
    for a, b in zip(lst, pattern):
        if a != b:
            return False
    return True

def get_idx(lst, pattern):   
    n = len(lst)
    m = len(pattern)
    rng = xrange(n - m)
    idx = -1
    for i in rng:
        if is_equal(lst[i:i+m], pattern):
            idx = i
            break;     
    return idx

def del_pat(lst, pattern):
    idx = get_idx(lst, pattern)
    ans = lst
    if idx > -1:
        a =  lst[:idx]
        a.extend(lst[idx + len(pattern):])
        ans = a
    return ans


Ответ 5

lst = [0,1,2,3,1,5,3,7]
tpl = (1,5,3)

# создаем строки из lst и tpl

s_lst = ""
for l in lst:
    s_lst += str(l)

s_tpl = ""
for t in tpl:
    s_tpl += str(t) 

# методом replace() производим замену всех вхождений s_tpl на "" в s_lst
# и делаем из обработанной строки список

new_lst = []
for i in s_lst.replace(s_tpl,""):
    new_lst.append(int(i))

print(new_lst)