Нужно удалить из списка в вхождения, да не просто по элементам, а прям множество. Т.е. если есть список: [0, 1, 2, 3, 1, 5, 3, 7]
, и например, кортеж, который удаляемых элементов (1, 5, 3)
, нужно, чтобы в итоге получился список [0, 1, 2, 3, 7]
. Как можно легче всего такое реализовать?
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)
[/apcode]
Добавлю и свой пример
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]
Фактически условие эквивалентно удалению подстроки из строки:
>>> 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).
Можно модифицировать алгоритм, чтобы принимать на вход произвольные итерируемые объекты, а не только последовательности. Или чтобы изменять входной список по месту без создания копии.
Я бы попробовал что-то вроде такого:
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 примерах, оба варианта рабочии.
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