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

La théorie des ensembles est inappropriée pour les listes, car les doublons donneront lieu à des réponses erronées avec la théorie des ensembles.

Par exemple :

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

n'a pas de sens. Oui, cela donne une réponse fausse mais ce n'est pas correct puisque la théorie des ensembles ne fait que comparer : 1,3,5 contre 1,3,4,5. Vous devez inclure tous les doublons.

Au lieu de cela, vous devez compter chaque occurrence de chaque élément et effectuer un contrôle supérieur à égal à. Cette opération n'est pas très coûteuse, car elle n'utilise pas O(N^2) opérations et ne nécessite pas de tri rapide.

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

En faisant tourner ça, on obtient :

$ python contained.py 
b in a:  False
b in a:  True

Answer 2

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

Si la liste 1 est dans la liste 2 :

• (x in two for x in one) génère une liste de True .

• quand nous faisons un set(x in two for x in one) n'a qu'un seul élément (True).

Answer 3

Pardonnez-moi si je suis en retard à la fête ;)

Pour vérifier si un set A est un sous-ensemble de set B , Python a A.issubset(B) y A <= B . Il fonctionne sur set seulement et fonctionne très bien MAIS la complexité de la mise en œuvre interne est inconnue. Référence : https://docs.python.org/2/library/sets.html#set-objects

Je suis venu avec un algorithme pour vérifier si list A est un sous-ensemble de list B avec les remarques suivantes.

• Pour réduire la complexité de la recherche d'un sous-ensemble, je trouve qu'il est approprié de sort les deux listes d'abord avant de comparer les éléments pour se qualifier pour les sous-ensemble.

• Cela m'a aidé à break el loop lorsque la valeur de l'élément de la deuxième liste B[j] est supérieure à la valeur de l'élément de la première liste A[i] .

• last_index_j est utilisé pour démarrer loop sur list B là où il s'est arrêté la dernière fois. Cela permet d'éviter de recommencer les comparaisons à partir du début de list B (qui est, comme vous pouvez le deviner inutile, de commencer list B de index 0 dans les années suivantes iterations .)

• La complexité sera O(n ln n) chacun pour trier les deux listes et O(n) pour la vérification du sous-ensemble.
  O(n ln n) + O(n ln n) + O(n) = O(n ln n) .

• Le code a beaucoup de print pour voir ce qui se passe à chaque étape du processus. iteration de la loop . Ils sont destinés à la compréhension seulement.

Vérifier si une liste est un sous-ensemble d'une autre liste

is_subset = True;

A = [9, 3, 11, 1, 7, 2];
B = [11, 4, 6, 2, 15, 1, 9, 8, 5, 3];

print(A, B);

# skip checking if list A has elements more than list B
if len(A) > len(B):
    is_subset = False;
else:
    # complexity of sorting using quicksort or merge sort: O(n ln n)
    # use best sorting algorithm available to minimize complexity
    A.sort();
    B.sort();

    print(A, B);

    # complexity: O(n^2)
    # for a in A:
    #   if a not in B:
    #       is_subset = False;
    #       break;

    # complexity: O(n)
    is_found = False;
    last_index_j = 0;

    for i in range(len(A)):
        for j in range(last_index_j, len(B)):
            is_found = False;

            print("i=" + str(i) + ", j=" + str(j) + ", " + str(A[i]) + "==" + str(B[j]) + "?");

            if B[j] <= A[i]:
                if A[i] == B[j]:
                    is_found = True;
                last_index_j = j;
            else:
                is_found = False;
                break;

            if is_found:
                print("Found: " + str(A[i]));
                last_index_j = last_index_j + 1;
                break;
            else:
                print("Not found: " + str(A[i]));

        if is_found == False:
            is_subset = False;
            break;

print("subset") if is_subset else print("not subset");

Sortie

[9, 3, 11, 1, 7, 2] [11, 4, 6, 2, 15, 1, 9, 8, 5, 3]
[1, 2, 3, 7, 9, 11] [1, 2, 3, 4, 5, 6, 8, 9, 11, 15]
i=0, j=0, 1==1?
Found: 1
i=1, j=1, 2==1?
Not found: 2
i=1, j=2, 2==2?
Found: 2
i=2, j=3, 3==3?
Found: 3
i=3, j=4, 7==4?
Not found: 7
i=3, j=5, 7==5?
Not found: 7
i=3, j=6, 7==6?
Not found: 7
i=3, j=7, 7==8?
not subset

Answer 4

Le code ci-dessous vérifie si un ensemble donné est un "sous-ensemble propre" d'un autre ensemble

 def is_proper_subset(set, superset):
     return all(x in superset for x in set) and len(set)<len(superset)

Answer 5

En python 3.5, vous pouvez faire un [*set()][index] pour obtenir l'élément. C'est une solution beaucoup plus lente que les autres méthodes.

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

result = set(x in two for x in one)

[*result][0] == True

ou juste avec len et set

len(set(a+b)) == len(set(a))