python - tuplas - Cómo eliminar cada aparición de sublista de la lista

print lista python

Question

Tengo dos listas:

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]

Quiero eliminar todas las ocurrencias de sub_list en big_list.

el resultado debería ser [2, 3, 4]

Para cadenas, podrías usar esto:

''2123124''.replace(''12'', '''')

Pero AFAIK esto no funciona para las listas.

Esto no es un duplicado de Eliminar una sublista de una lista porque quiero eliminar todas las sublistas de la lista grande. En la otra pregunta, el resultado debería ser [5,6,7,1,2,3,4] .

Actualización: por simplicidad tomé enteros en este ejemplo. Pero los elementos de la lista pueden ser objetos arbitrarios.

Actualización2:

si big_list = [1, 2, 1, 2, 1] y sub_list = [1, 2, 1] , quiero que el resultado sea [2, 1] (como ''12121''.replace(''121'', '''') )

Actualización3:

No me gusta copiar y pegar el código fuente de StackOverflow en mi código. Es por eso que creé la segunda pregunta en recomendaciones de software: https://softwarerecs.stackexchange.com/questions/51273/library-to-remove-every-occurrence-of-sub-list-from-list-python

Actualización4: si conoce una biblioteca para hacer esta llamada a un método, escríbalo como respuesta, ya que esta es mi solución preferida.

La prueba debería pasar esta prueba:

def test_remove_sub_list(self):
    self.assertEqual([1, 2, 3], remove_sub_list([1, 2, 3], []))
    self.assertEqual([1, 2, 3], remove_sub_list([1, 2, 3], [4]))
    self.assertEqual([1, 3], remove_sub_list([1, 2, 3], [2]))
    self.assertEqual([1, 2], remove_sub_list([1, 1, 2, 2], [1, 2]))
    self.assertEquals([2, 1], remove_sub_list([1, 2, 1, 2, 1], [1, 2, 1]))
    self.assertEqual([], remove_sub_list([1, 2, 1, 2, 1, 2], [1, 2]))

Answer 1

Lo que está tratando de lograr se puede hacer convirtiéndolo en una lista de cadenas y luego de volver a colocarlo, conviértalo en un tipo entero.

En una sola línea, puedes hacerlo así

map(int,list(("".join(map(str, big_list))).replace("".join(map(str, sub_list)),'''').replace(''''.join((map(str, sub_list))[::-1]),'''')))

Entrada

big_list = [1, 2, 1, 2, 1]
sub_list = [1, 2, 1]

Salida

[2, 1]

Entrada

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]

Ouput

[2, 3, 4]

Answer 2

Más legible que cualquier anterior y sin memoria adicional:

def remove_sublist(sublist, mainlist):

    cursor = 0

    for b in mainlist:
        if cursor == len(sublist):
            cursor = 0
        if b == sublist[cursor]:
            cursor += 1
        else:
            cursor = 0
            yield b

    for i in range(0, cursor):
        yield sublist[i]

Esto es para onliner si quieres una función de la biblioteca, deja que sea esto

[x for x in remove_sublist([1, 2], [2, 1, 2, 3, 1, 2, 4])]

Answer 3

Prueba del y slicing . La peor complejidad de tiempo es O(N^2) .

sub_list=[''a'', int]
big_list=[1, ''a'', int, 3, float, ''a'', int, 5]
i=0
while i < len(big_list):
    if big_list[i:i+len(sub_list)]==sub_list:
        del big_list[i:i+len(sub_list)]
    else:
        i+=1

print(big_list)

resultado:

[1, 3, <class ''float''>, 5]

Answer 4

Puede usar la recursión con un generador:

def remove(d, sub_list):
   if d[:len(sub_list)] == sub_list and len(sub_list) <= len(d[:len(sub_list)]):
      yield from [[], remove(d[len(sub_list):], sub_list)][bool(d[len(sub_list):])]
   else:
      yield d[0]
      yield from [[], remove(d[1:], sub_list)][bool(d[1:])]

tests = [[[2, 1, 2, 3, 1, 2, 4], [1, 2]], [[1, 2, 1, 2], [1, 2]], [[1, ''a'', int, 3, float, ''a'', int, 5], [''a'', int]], [[1, 1, 1, 1, 1], [1,1,1]]]
for a, b in tests:
  print(list(remove(a, b)))

Salida:

[2, 3, 4]
[]
[1, 3, <class ''float''>, 5]
[1, 1]

Answer 5

Qué tal esto:

def remove_sublist(lst, sub):
    max_ind_sub = len(sub) - 1
    out = []
    i = 0
    tmp = []

    for x in lst:
        if x == sub[i]:
            tmp.append(x)
            if i < max_ind_sub: # partial match 
                i += 1
            else:  # found complete match
                i = 0
                tmp = []
        else:
            if tmp:  # failed partial match 
                i = 0
                out += tmp
            if x == sub[0]:  # partial match
                i += 1
                tmp = [x]
            else:
                out.append(x)

    return out

Actuación:

lst = [2, 1, 2, 3, 1, 2, 4]
sub = [1, 2]
%timeit remove_sublist(lst, sub)  # solution of Mad Physicist
%timeit remove_sublist_new(lst, sub)
>>> 2.63 µs ± 112 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> 1.77 µs ± 13.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Actualizar

Mi primera solución tenía un error. Pude arreglarlo (actualicé mi código anterior) pero el método parece mucho más complicado ahora. En términos de rendimiento, sigue siendo mejor que la solución de Mad Physicist en mi máquina local.

Answer 6

Solo por diversión, esta es la aproximación más aproximada a un one-liner:

from functools import reduce

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]
result = reduce(lambda r, x: r[:1]+([1]+r[2:-r[1]],[min(len(r[0]),r[1]+1)]+r[2:])[r[-r[1]:]!=r[0]]+[x], big_list+[0], [sub_list, 1])[2:-1]

No confíes en que funciona? ¡Compruébalo en IDEone !

Por supuesto, está lejos de ser eficiente y es desagradablemente críptico, sin embargo, debería ayudar a convencer al OP para que acepte la respuesta de @Mad Physicist .

Answer 7

Tan compacto como puedo:

a=[]
for i in range(0,len(big_list)):
    if big_list[i]==1 and big_list[i+1]==2:
        a.extend((i,i+1))
[big_list[x] for x in [x for x in range(len(big_list)) if x not in a]]

Out[101]: [2, 3, 4]

Mismo enfoque en R:

big_list <- c(2, 1, 2, 3, 1, 2, 4)
sub_list <- c(1,2)

a<-c()
for(i in 1:(length(big_list)-1)){if (all(big_list[c(i,i+1)]==sub_list)) a<-c(a,c(i,i+1)) }
big_list[-a]
[1] 2 3 4

Creo que R es más fácil.

[big_list[x] for x in [x for x in range(len(big_list)) if x not in a]] es equivalente a big_list[-a]

Answer 8

Tendría que implementarlo usted mismo. Aquí está la idea básica:

def remove_sublist(lst, sub):
    i = 0
    out = []
    while i < len(lst):
        if lst[i:i+len(sub)] == sub:
            i += len(sub)
        else:
            out.append(lst[i])
            i += 1
    return out

Esto explica cada elemento de la lista original y lo agrega a una lista de salida si no es miembro del subconjunto. Esta versión no es muy eficiente, pero funciona como el ejemplo de cadena que proporcionó, en el sentido de que crea una nueva lista que no contiene su subconjunto. También funciona para tipos de elementos arbitrarios, siempre que admitan == . Eliminar [1,1,1] de [1,1,1,1] dará como resultado [1] , como para una cadena.

Aquí hay un enlace IDEOne que muestra el resultado de

>>> remove_sublist([1, ''a'', int, 3, float, ''a'', int, 5], [''a'', int])
[1, 3, <class ''float''>, 5]

Answer 9

Un enfoque diferente en Python 2.x!

from more_itertools import locate, windowed
big_list = [1, 2, 1, 2, 1]
sub_list = [1, 2, 1]

"""
Fetching all starting point of indexes (of sub_list in big_list)
to be removed from big_list. 
"""

i = list(locate(windowed(big_list, len(sub_list)), pred=lambda x: x==tuple(sub_list)))

""" 
Here i comes out to be [0, 2] in above case. But index from 2 which 
includes 1, 2, 1 has last 1 from the 1st half of 1, 2, 1 so further code is
to handle this case.
PS: this won''t come for-
big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]
as here i comes out to be [1, 4]
"""

# The further code.
to_pop = []
for ele in i:
    if to_pop:
        if ele == to_pop[-1]:
            continue
    to_pop.extend(range(ele, ele+len(sub_list)))

# Voila! to_pop consists of all the indexes to be removed from big_list.

# Wiping out the elements!
for index in sorted(to_pop, reverse=True):
    del big_list[index]

Tenga en cuenta que debe eliminarlos en orden inverso para que no descarte los índices posteriores.

En Python3, la firma de locate () será diferente.

Answer 10

Un enfoque recursivo:

def remove(lst, sub):
    if not lst:
        return []
    if lst[:len(sub)] == sub:
        return remove(lst[len(sub):], sub)
    return lst[:1] + remove(lst[1:], sub)
print(remove(big_list, sub_list))

Esto produce:

[2, 3, 4]

Answer 11

Una versión mejorada para verificar si lst[i:i+len(sub)] < len(lst)

def remove_sublist(lst, sub):
    i = 0
    out = []
    sub_len = len(sub)
    lst_len = len(lst)
    while i < lst_len:
        if (i+sub_len) < lst_len:
            if lst[i: i+sub_len] == sub:
                i += sub_len
            else:
                out.append(lst[i])
                i += 1
        else:
            out.append(lst[i])
            i += 1

    return out

Answer 12

Use itertools.zip_longest para crear tuplas de elementos (donde n es la longitud de sub_list) y luego filtre el elemento actual y los siguientes elementos n-1 cuando uno de los elementos coincida con la sub_list

>>> from itertools import zip_longest, islice
>>> itr = zip_longest(*(big_list[i:] for i in range(len(sub_list))))
>>> [sl[0] for sl in itr if not (sl == tuple(sub_list) and next(islice(itr, len(sub_list)-2, len(sub_list)-1)))]
[2, 3, 4]

Para mejorar la eficiencia, puede calcular tuple(sub_list) y len(sub_list) antes de comenzar a filtrar

>>> l = len(sub_list)-1
>>> tup = tuple(sub_list)
>>> [sl[0] for sl in itr if not (sl == tup and next(islice(itr, l-1, l)))]
[2, 3, 4]

Answer 13

(Para el enfoque final, vea el último fragmento de código)

Pensé que una simple conversión de cadenas sería suficiente:

big_list = [2, 1, 2, 3, 1, 2, 4]
sub_list = [1, 2]

new_list = list(map(int, list((''''.join(map(str, big_list))).replace((''''.join(map(str, sub_list))), ''''))))

Básicamente estoy haciendo una búsqueda / reemplazo con los equivalentes de cadena de las listas. Los estoy asignando a números enteros para que se conserven los tipos originales de las variables. Esto funcionará para cualquier tamaño de las listas grandes y secundarias.

Sin embargo, es probable que esto no funcione si lo llamas sobre objetos arbitrarios si no tienen una representación textual. Además, este método da como resultado que solo se retenga la versión textual de los objetos; esto es un problema si los tipos de datos originales deben mantenerse.

Para esto, he compuesto una solución con un enfoque diferente:

new_list = []
i = 0
while new_list != big_list:
    if big_list[i:i+len(sub_list)] == sub_list:
        del big_list[i:i+len(sub_list)]
    else:
        new_list.append(big_list[i])
        i += 1

Esencialmente, estoy eliminando cada duplicado de la sub_list cuando los encuentro y anexo a la new_list cuando encuentro un elemento que no es parte de un duplicado. Cuando new_list y big_list son iguales, se han encontrado todos los duplicados, que es cuando paro. No he usado una prueba, excepto porque no creo que haya errores de indexación.

Esto es similar a la respuesta de @ MadPhysicist y tiene aproximadamente la misma eficacia, pero la mía consume menos memoria .

Este segundo enfoque funcionará para cualquier tipo de objeto con cualquier tamaño de listas y, por lo tanto, es mucho más flexible que el primer enfoque. Sin embargo, el primer enfoque es más rápido si sus listas son solo números enteros.

Sin embargo, ¡aún no he terminado! ¡He inventado una lista de comprensión de una sola línea que tiene la misma funcionalidad que el segundo enfoque!

import itertools
new_list = [big_list[j] for j in range(len(big_list)) if j not in list(itertools.chain.from_iterable([ list(range(i, i+len(sub_list))) for i in [i for i, x in enumerate(big_list) if x == sub_list[0]] if big_list[i:i+len(sub_list)] == sub_list ]))]

Inicialmente, esto parece desalentador, ¡pero te aseguro que es bastante simple! Primero, creo una lista de los índices donde ha ocurrido el primer elemento de la sublista. Luego, para cada uno de estos índices, verifico si los siguientes elementos forman la sublista. Si lo hacen, el rango de índices que forman el duplicado de la sublista se agrega a otra lista. Después, utilizo una función de itertools para aplanar la lista resultante de listas. Cada elemento en esta lista aplanada es un índice que está en un duplicado de la sublista. Finalmente, creo una new_list que consta de cada elemento de big_list que tiene un índice no encontrado en la lista aplanada.

No creo que este método esté en ninguna de las otras respuestas. Me gusta más, ya que es bastante limpio una vez que te das cuenta de cómo funciona y es muy eficiente (debido a la naturaleza de las listas de comprensión).

Answer 14

Actualización : la biblioteca more_itertools ha lanzado more_itertool.replace , una herramienta que resuelve este problema en particular (ver Opción 3).

Primero, aquí hay algunas otras opciones que funcionan en iterables genéricos (listas, cadenas, iteradores, etc.):

Código

Opción 1 - sin bibliotecas :

def remove(iterable, subsequence):
    """Yield non-subsequence items; sans libraries."""
    seq = tuple(iterable)
    subsequence = tuple(subsequence)
    n = len(subsequence)
    skip = 0

    for i, x in enumerate(seq):
        slice_ = seq[i:i+n]
        if not skip and (slice_ == subsequence):
            skip = n
        if skip:
            skip -= 1
            continue
        yield x   

Opción 2: con more_itertools

import more_itertools as mit


def remove(iterable, subsequence):
    """Yield non-subsequence items."""
    iterable = tuple(iterable)
    subsequence = tuple(subsequence)
    n = len(subsequence)
    indices = set(mit.locate(mit.windowed(iterable, n), pred=lambda x: x == subsequence))

    it_ = enumerate(iterable)
    for i, x in it_:
        if i in indices:
            mit.consume(it_, n-1)
        else:
            yield x

Manifestación

list(remove(big_list, sub_list))
# [2, 3, 4]

list(remove([1, 2, 1, 2], sub_list))
# []

list(remove([1, "a", int, 3, float, "a", int, 5], ["a", int]))
# [1, 3, float, 5]

list(remove("11111", "111"))
# [''1'', ''1'']

list(remove(iter("11111"), iter("111")))
# [''1'', ''1'']

Opción 3: con more_itertool.replace :

Manifestación

pred = lambda *args: args == tuple(sub_list)
list(mit.replace(big_list, pred=pred, substitutes=[], window_size=2))
# [2, 3, 4]

pred=lambda *args: args == tuple(sub_list)
list(mit.replace([1, 2, 1, 2], pred=pred, substitutes=[], window_size=2))
# []

pred=lambda *args: args == tuple(["a", int])
list(mit.replace([1, "a", int, 3, float, "a", int, 5], pred=pred, substitutes=[], window_size=2))
# [1, 3, float, 5]

pred=lambda *args: args == tuple("111")
list(mit.replace("11111", pred=pred, substitutes=[], window_size=3))
# [''1'', ''1'']

pred=lambda *args: args == tuple(iter("111"))
list(mit.replace(iter("11111"), pred=pred, substitutes=[], window_size=3))
# [''1'', ''1'']

Detalles

En todos estos ejemplos, estamos escaneando la secuencia principal con segmentos de ventana más pequeños. Cedemos lo que no se encuentra en la porción y omitimos lo que está en la porción.

Opción 1 - sin bibliotecas

Iterar una secuencia enumerada y evaluar las porciones de tamaño n (la longitud de la subsecuencia). Si el próximo segmento es igual a la subsecuencia, restablezca el skip y ceda el elemento. De lo contrario, repita el paso. skip pistas cuántas veces para avanzar el bucle, por ejemplo, la sublist es de tamaño n=2 , por lo que se salta dos veces por partido.

Tenga en cuenta que puede convertir esta opción para trabajar solo con sequences eliminando las dos primeras asignaciones de tuplas y reemplazando el parámetro iterable con seq , por ejemplo def remove(seq, subsequence):

Opción 2: con more_itertools

Los índices se encuentran para cada subsecuencia coincidente en un iterable. Al iterar un iterador enumerado, si se encuentra un índice en los indices , la subsecuencia restante se omite al consumir los siguientes n-1 elementos del iterador. De lo contrario, se produce un artículo.

Instale esta biblioteca a través de > pip install more_itertools .

Opción 3: con more_itertool.replace :

Esta herramienta reemplaza una subsecuencia de elementos definidos en un predicado con valores sustitutos. Para eliminar elementos, sustituimos un contenedor vacío, por ejemplo, substitutes=[] . La longitud de los elementos reemplazados se especifica mediante el parámetro window_size (este valor es igual a la longitud de la window_size ).