Jak mogę sprawdzić, czy jedna lista jest podzbiorem innej?

Muszę sprawdzić, czy lista jest podzbiorem innego - szukam zwrotu boolowskiego.

Czy testowanie równości na mniejszej liście po skrzyżowaniu jest najszybszym sposobem na to? Wydajność ma ogromne znaczenie, biorąc pod uwagę liczbę zestawów danych, które należy porównać.

Dodanie dalszych faktów na podstawie dyskusji:

1. Czy któraś z list będzie taka sama dla wielu testów? Robi to, ponieważ jednym z nich jest statyczna tabela odnośników.

2. Czy to musi być lista? Tak nie jest - statyczna tabela odnośników może być czymkolwiek, co działa najlepiej. Dynamiczny to dykt, z którego wyodrębniamy klucze w celu przeprowadzenia wyszukiwania statycznego.

Jakie byłoby optymalne rozwiązanie biorąc pod uwagę scenariusz?

Funkcja wykonawcza, którą zapewnia Python, to set.issubset. Ma jednak kilka ograniczeń, które sprawiają, że nie jest jasne, czy jest to odpowiedź na twoje pytanie.

Lista może zawierać elementy wiele razy i ma określoną kolejność. Zestaw nie. Dodatkowo zestawy działają tylko na obiektach mieszających się .

Czy pytasz o podzbiór lub podsekwencję (co oznacza, że ​​będziesz potrzebować algorytmu wyszukiwania ciągu)? Czy któraś z list będzie taka sama dla wielu testów? Jakie typy danych są zawarte na liście? A jeśli chodzi o to, czy musi to być lista?

Twój drugi post przecina dykt, a lista wyjaśniła typy i otrzymała zalecenie użycia widoków klucza słownika dla ich funkcji podobnej do zestawu. W takim przypadku wiadomo, że działa, ponieważ klucze słownika zachowują się jak zestaw (do tego stopnia, że ​​zanim mieliśmy zestawy w Pythonie korzystaliśmy ze słowników). Można się zastanawiać, jak problem stał się mniej szczegółowy w ciągu trzech godzin.

>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

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

all(x in two for x in one)

Objaśnienie: Generator tworzy wartości logiczne, przeglądając listę, onesprawdzając, czy ten element znajduje się na liście two. all()zwraca, Truejeśli każdy element jest prawdziwy, w przeciwnym razie False.

Zaletą jest również to, że allzwraca False przy pierwszym wystąpieniu brakującego elementu, zamiast konieczności przetwarzania każdego elementu.

Zakładając, że przedmioty są haszowalne

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

Jeśli nie obchodzą Cię duplikaty przedmiotów, np. [1, 2, 2]a [1, 2]następnie użyj:

>>> set([1, 2, 2]).issubset([1, 2])
True

Czy testowanie równości na mniejszej liście po skrzyżowaniu jest najszybszym sposobem na to?

.issubsetbędzie najszybszym sposobem na zrobienie tego. Sprawdzanie długości przed testowaniem issubsetnie poprawi prędkości, ponieważ nadal masz O (N + M) elementów do iteracji i sprawdzania.

Jeszcze jednym rozwiązaniem byłoby użycie intersection.

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

set(one).intersection(set(two)) == set(one)

Przecięcie zbiorów zawierałoby set one

(LUB)

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

set(one) & (set(two)) == set(one)

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

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

Jeśli lista 1 znajduje się na liście 2:

• (x in two for x in one)generuje listę True.

• kiedy robimy, set(x in two for x in one)ma tylko jeden element (prawda).

Teoria zestawów jest nieodpowiednia dla list, ponieważ duplikaty skutkują błędnymi odpowiedziami przy użyciu teorii zbiorów.

Na przykład:

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

Nie ma znaczenia. Tak, daje fałszywą odpowiedź, ale nie jest to poprawne, ponieważ teoria mnogości po prostu porównuje: 1,3,5 wobec 1,3,4,5. Musisz dołączyć wszystkie duplikaty.

Zamiast tego musisz policzyć każde wystąpienie każdego elementu i wykonać sprawdzenie większe niż równe. Nie jest to bardzo drogie, ponieważ nie wykorzystuje operacji O (N ^ 2) i nie wymaga szybkiego sortowania.

#!/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)

Następnie uruchamiając to otrzymujesz:

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

Ponieważ nikt nie rozważał porównania dwóch ciągów, oto moja propozycja.

Możesz oczywiście chcieć sprawdzić, czy potok („|”) nie jest częścią żadnej listy i może automatycznie wybrał inny znak, ale masz pomysł.

Użycie pustego ciągu jako separatora nie jest rozwiązaniem, ponieważ liczby mogą mieć kilka cyfr ([12,3]! = [1,23])

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

Wybacz mi, jeśli spóźnię się na przyjęcie. ;)

Aby sprawdzić, czy jeden set Ajest podzbiorem set B, Pythonma A.issubset(B)i A <= B. Działa settylko i działa świetnie, ALE złożoność implementacji wewnętrznej jest nieznana. Odniesienie: https://docs.python.org/2/library/sets.html#set-objects

Wymyśliłem algorytm, aby sprawdzić, czy list Ajest podzbiorem list Bnastępujących uwag.

• Aby zmniejszyć złożoność wyszukiwania podzbioru, uważam, że należy sortnajpierw porównać obie listy przed porównaniem elementów w celu zakwalifikowania do podzbioru.
• To pomogło mi gdy wartość elementu drugiej listy jest większa niż wartość elementu pierwszej listy .breakloopB[j]A[i]
• last_index_jsłuży do rozpoczynania loopod list Bmiejsca, w którym zostało ostatnio przerwane. Pomaga uniknąć rozpoczynania porównań od początku list B(co, jak można się domyślać, jest niepotrzebne, zaczyna list Bod index 0następnego iterations).

• Złożoność będzie polegać O(n ln n)na sortowaniu obu list i O(n)sprawdzaniu podzbioru.
  O(n ln n) + O(n ln n) + O(n) = O(n ln n).

• Kod zawiera wiele printinstrukcji, aby zobaczyć, co się dzieje w każdym iterationz nich loop. Są one przeznaczone wyłącznie do zrozumienia.

Sprawdź, czy jedna lista jest podzbiorem innej listy

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

Wynik

[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

Poniższy kod sprawdza, czy dany zestaw jest „właściwym podzbiorem” innego zestawu

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

W Pythonie 3.5 możesz zrobić a, [*set()][index]aby uzyskać element. Jest to znacznie wolniejsze rozwiązanie niż inne metody.

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

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

[*result][0] == True

lub po prostu z Len i Set

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

Oto skąd wiem, że jeśli jedna lista jest podzbiorem innej, sekwencja ma dla mnie znaczenie.

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

Większość rozwiązań uważa, że ​​listy nie mają duplikatów. Jeśli Twoje listy zawierają duplikaty, możesz spróbować:

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

Zapewnia, że ​​lista podrzędna nigdy nie zawiera innych elementów niż lista lub większa część wspólnego elementu.

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

Jeśli pytasz, czy jedna lista jest „zawarta” na innej liście, to:

>>>if listA in listB: return True

Jeśli pytasz, czy każdy element na liście A ma taką samą liczbę pasujących elementów na liście B, spróbuj:

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

Jeśli a2 is subset of a1takLength of set(a1 + a2) == Length of set(a1)

a1 = [1, 2, 3, 4, 5]
a2 = [1, 2, 3]

len(set(a1)) == len(set(a1 + a2))