Comment puis-je vérifier si une liste est un sous-ensemble d'une autre ?

Question

Je dois vérifier si une liste est un sous-ensemble d'une autre - un retour booléen est tout ce que je recherche.

Le test d'égalité sur la plus petite liste après une intersection est-il le moyen le plus rapide de le faire ? Les performances sont de la plus haute importance étant donné le nombre d'ensembles de données qui doivent être comparés.

Ajout de faits supplémentaires sur la base des discussions :

1. L'une ou l'autre de ces listes sera-t-elle la même pour de nombreux tests ? Oui, car l'une d'entre elles est une table de consultation statique.

2. Doit-il s'agir d'une liste ? Non, la table de consultation statique peut être tout ce qui est le plus performant. La table dynamique est un dict dont nous extrayons les clés pour effectuer une recherche statique.

Quelle serait la solution optimale compte tenu du scénario ?

Answer 1

Voici comment je sais si une liste est un sous-ensemble d'une autre, la séquence m'importe dans mon cas.

def is_subset(list_long,list_short):
    short_length = len(list_short)
    subset_list = []
    for i in range(len(list_long)-short_length+1):
        subset_list.append(list_long[i:i+short_length])
    if list_short in subset_list:
        return True
    else: return False

Answer 2

Puisque personne n'a envisagé de comparer deux chaînes de caractères, voici ma proposition.

Vous pouvez bien sûr vérifier que la barre verticale ("|") ne fait pas partie de l'une ou l'autre des listes et choisir automatiquement un autre caractère, mais vous avez compris l'idée.

L'utilisation d'une chaîne vide comme séparateur n'est pas une solution car les nombres peuvent avoir plusieurs chiffres ([12,3] != [1,23]).

def issublist(l1,l2):
    return '|'.join([str(i) for i in l1]) in '|'.join([str(i) for i in l2])

Answer 3

Si vous demandez si une liste est "contenue" dans une autre liste, alors.. :

>>>if listA in listB: return True

Si vous demandez si chaque élément de la liste A a un nombre égal d'éléments correspondants dans la liste B, essayez :

all(True if listA.count(item) <= listB.count(item) else False for item in listA)

Answer 4

La plupart des solutions considèrent que les listes ne comportent pas de doublons. Si vos listes ont des doublons, vous pouvez essayer ceci :

def isSubList(subList,mlist):
    uniqueElements=set(subList)
    for e in uniqueElements:
        if subList.count(e) > mlist.count(e):
            return False     
    # It is sublist
    return True

Il garantit que la sous-liste ne contient jamais d'éléments différents de ceux de la liste ou une plus grande quantité d'un élément commun.

lst=[1,2,2,3,4]
sl1=[2,2,3]
sl2=[2,2,2]
sl3=[2,5]

print(isSubList(sl1,lst)) # True
print(isSubList(sl2,lst)) # False
print(isSubList(sl3,lst)) # False