46 votes

Comment supprimer toutes les occurrences d'une sous-liste d'une liste ?

J'ai deux listes :

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

Je veux supprimer toutes les occurrences de sub_list dans big_list.

Le résultat devrait être [2, 3, 4]

Pour les chaînes de caractères, vous pouvez utiliser ceci :

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

Mais AFAIK, cela ne fonctionne pas pour les listes.

Il ne s'agit pas d'un doublon de Suppression d'une sous-liste d'une liste puisque je veux supprimer toutes les sous-listes de la grande liste. Dans l'autre question, le résultat devrait être [5,6,7,1,2,3,4] .

Mise à jour : Pour simplifier, j'ai pris des entiers dans cet exemple. Mais les éléments de la liste pourraient être des objets arbitraires.

Mise à jour2 :

si big_list = [1, 2, 1, 2, 1] y sub_list = [1, 2, 1] , Je veux que le résultat soit [2, 1] (comme '12121'.replace('121', '') )

Mise à jour3 :

Je n'aime pas copier et coller le code source de StackOverflow dans mon code. C'est pourquoi j'ai créé une deuxième question à software-recommendations : https://softwarerecs.stackexchange.com/questions/51273/library-to-remove-every-occurrence-of-sub-list-from-list-python

Mise à jour 4 : si vous connaissez une bibliothèque permettant de faire cet appel de méthode unique, veuillez l'écrire comme réponse, car c'est ma solution préférée.

Le test doit réussir ce test :

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]))

2 votes

1 votes

Si vous n'avez que des entiers dans la liste, vous pouvez procéder à une conversion en chaînes de caractères : list(map(int, (''.join(map(str, big_list)).replace(''.join(map(str, sub_list)), '')))) . Ou voulez-vous appliquer cela à des objets arbitraires ?

2 votes

Juste pour clarifier, si vous avez big_list = [1, 2, 1, 2, 1] y sub_list = [1, 2, 1] voulez-vous que le résultat soit [2, 1] o [] (c'est-à-dire supprimer par occurrence ou supprimer tous les éléments qui correspondent à l'élément sub_list ) ?

25voto

Mad Physicist Points 3218

Vous devez le mettre en œuvre vous-même. Voici l'idée de base :

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

Cette opération parcourt chaque élément de la liste originale et l'ajoute à une liste de sortie s'il ne fait pas partie du sous-ensemble. Cette version n'est pas très efficace, mais elle fonctionne comme l'exemple de chaîne que vous avez fourni, dans le sens où elle crée une nouvelle liste ne contenant pas votre sous-ensemble. Elle fonctionne également pour des types d'éléments arbitraires, du moment qu'ils supportent == . Retrait de [1,1,1] de [1,1,1,1] aura pour résultat correct [1] comme pour une chaîne de caractères.

Voici un Lien IDEOne montrant le résultat de

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

1 votes

Allez, vous pouvez faire mieux que ça ! =)

0 votes

@lenik. C'est vrai. J'espère que c'est moins paresseux. Je n'ai pas pu trouver de solution plus rationnelle, malheureusement. Et le faire en place n'allait pas être plus joli.

0 votes

Pas de problème, il semble que votre solution soit la seule qui reste =)

14voto

Marcus.Aurelianus Points 1369

Essayez del y slicing . La pire complexité temporelle est 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)

résultat :

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

0 votes

Ce n'est pas correct. Essayez sub_list = [1, 2] y big_list = [1, 2, 1, 2] . Le résultat devrait être [] mais vous obtenez [1, 2] . Si vous supprimez sur place, vous devez revenir en arrière.

1 votes

@Mad Physicist , mis à jour, passé, esprit changer votre downvote ?

1 votes

Oui, c'est très bien. Sans doute meilleur que le mien.

8voto

blhsing Points 57682

Une approche récursive :

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))

Ces sorties :

[2, 3, 4]

1 votes

Ce n'est pas super efficace, mais très soigné.

6voto

mingganz Points 353

Une version améliorée pour vérifier 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

0 votes

Cette situation n'est pas améliorée en termes de lisibilité. Les sous-séquences courtes à la fin ne seront jamais égales à sub de toute façon et la liste est suffisamment intelligente pour vérifier d'abord la longueur pour ==.

0 votes

Vous rendez le contrôle plus difficile à lire. et moins efficace.

1 votes

Si la liste 'sub' est grande, je pense que 'if (i+sub_len) < lst_len' devrait être plus efficace que 'if lst[i : i+sub_len] == sub' du point de vue de la performance. En effet, 'lst[i : i+sub_len]' devra générer une liste et cela coûtera de la mémoire, non ?

6voto

RandomDude Points 473

Que dites-vous de ça ?

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

Performance :

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)

Mise à jour

Ma première solution avait un bug. J'ai pu le corriger (j'ai mis à jour mon code ci-dessus) mais la méthode semble beaucoup plus compliquée maintenant. En termes de performances, elle est quand même meilleure que la solution de Physicien fou sur ma machine locale.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X