Jak ustalić, czy lista jest podzbiorem innej listy?

Question

Jaki jest skuteczny sposób określenia, czy lista jest podzbiorem innej listy?

Przykład:

is_subset(List(1,2,3,4),List(2,3)) //Returns true 
is_subset(List(1,2,3,4),List(3,4,5)) //Returns false 

ja przeważnie szukają wydajnego algorytmu i nie jest zbyt problemem jak lista jest przechowywana. Może być przechowywany w tablicy, liście linków lub innej strukturze danych.

Dzięki

EDIT: Lista jest posortowana

Answer 1

Jeśli jesteś ok z przechowywaniem danych w HashSet można po prostu sprawdzić, czy list1 zawiera x dla każdego x w listy2. Które będą zbliżone do O (n) w rozmiarze listy2. (Oczywiście możesz zrobić to samo z innymi strukturami danych, ale to spowoduje różne czasy działania).

Answer 2

To zależy w dużym stopniu od języka/zestawu narzędzi, a także od wielkości i miejsca przechowywania list.

Jeśli listy są posortowane, pojedyncza pętla może to określić. Możesz po prostu zacząć iść na większą listę, próbując znaleźć pierwszy element z mniejszej listy (break, jeśli przekazujesz ją wartości), a następnie przejść do następnej i kontynuować od bieżącej lokalizacji. Jest to szybkie, ponieważ jest to algorytm z jedną pętlą/jednym przejściem.

W przypadku niesortowanych list często najszybciej buduje się jakąś formę tablicy haszującej z elementów pierwszej listy, a następnie przeszukuje każdy element na drugiej liście z wartości mieszania. Jest to podejście, które wiele rozszerzeń .NET LINQ wykorzystuje wewnętrznie do wyszukiwania przedmiotów na liście i skaluje się całkiem dobrze (chociaż mają dość duże wymagania dotyczące pamięci tymczasowej).

Answer 3

Jeśli obie listy są uporządkowane, jednym prostym rozwiązaniem byłoby jednoczesne przejrzenie obu list (z dwoma wskaźnikami nierówności na obu listach) i sprawdzenie, czy wszystkie elementy na drugiej liście znajdują się na pierwszej liście (do wszystkie elementy zostaną znalezione lub dopóki nie osiągniesz większej liczby na pierwszej liście).

pseudo-kod w C++ będzie wyglądać mniej więcej tak:

List l1, l2; 
iterator i1 = l1.start(); 
iterator i2 = l2.start(); 
while(i1 != l1.end() && i2 != l2.end()) { 
    if (*i1 == *i2) { 
    i1++; 
    i2++; 
    } else if (*i1 > *i2) { 
    return false; 
    } else { 
    i1++; 
    } 
} 
return true; 

(To oczywiście nie będzie działać jak jest, ale idea powinny być jasne).

Jeśli lista nie jest uporządkowana, można użyć hashtable - wstawić wszystkie elementy na pierwszej liście, a następnie sprawdzić, czy wszystkie elementy z drugiej listy znajdują się w tablicy hashtable.

Są to odpowiedzi algorytmiczne. W różnych językach istnieją domyślne wbudowane metody sprawdzania tego.

Answer 4

Wydajny algorytm wykorzystuje jakieś machiny państwowej, gdzie można zachować w pamięci stany akceptujące (w Pythonie):

def is_subset(l1, l2): 
    matches = [] 
    for e in l1: 
     # increment 
     to_check = [0] + [i+1 for i in matches] 
     matches = [] # nothing matches 
     for i in to_check: 
      if l2[i] = e: 
       if i == len(l2)-1: 
        return True 
       matches.append(i) 
    return False 

EDIT: oczywiście, jeśli lista jest posortowana, nie trzeba, że algorytm, po prostu wykonaj:

def is_subset(l1, l2): 
    index = 0 
    for e in l1: 
     if e > l2[index]: 
      return False 
     elif e == l2[index]: 
      index += 1 
     else: 
      index == 0 
     if index == len(l2): 
      return True 
    return False 

Answer 5

Powinieneś rzucić okiem na wdrożenie metody wyszukiwania STL. Tak wygląda C++, jak sądzę.

http://www.sgi.com/tech/stl/search.html

Opis

wyszukiwania znajduje podciąg w przedziale [first1, last1), który jest identyczny [first2, last2) w porównaniu element po elemencie.

Answer 6

Chciałem tylko wspomnieć, że Python ma sposobu na to:

return set(list2).issubset(list1) 

czyli

return set(list2) <= set(list1) 

Answer 7

Jeżeli obawiasz się o zamówienie lub ciągłości, może trzeba użyć Boyer-Moore lub the Horspool algorithm.

Pytanie brzmi, czy chcesz uwzględnić [2, 1] za podzbiór [1, 2, 3]? Czy chcesz [1, 3] uważać za podzbiór [1, 2, 3]? Jeśli odpowiedź nie dotyczy obu, możesz rozważyć jeden z wyżej wymienionych algorytmów. W przeciwnym razie możesz rozważyć zestaw skrótu.

Answer 8

dla C++, najlepszym sposobem jest użycie std::includes algorytmu:

#include <algorithm> 

std::list<int> l1, l2; 
... 
// Test whether l2 is a subset of l1 
bool is_subset = std::includes(l1.begin(), l1.end(), l2.begin(), l2.end()); 

wymaga to oba wykazy mają być sortowane, jak określono w swoim pytaniu. Złożoność jest liniowa.

Answer 9

func isSubset (@list, @possibleSubsetList) { 
    if (size (@possibleSubsetList) > size (@list)) { 
     return false; 
    } 
    for (@list : $a) { 
     if ($a != @possibleSubsetList[0]) { 
      next; 
     } else { 
      pop (@possibleSubsetList); 
     } 
    } 
    if (size (@possibleSubsetList) == 0) { 
     return true; 
    } else { 
     return false; 
    } 
} 

O (n) altówka. Oczywiście isSubset ((1,2,3,4,5), (2,4)) zwróci prawdziwą

Answer 10

Scala, zakładając, że masz na myśli podciąg przez podzbioru:

def is_subset[A,B](l1: List[A], l2: List[B]): Boolean = 
    (l1 indexOfSeq l2) > 0 

Zresztą podciąg to tylko problem z podciąganiami. Optymalne algorytmy to Knuth-Morris-Pratt i Boyer-Moore oraz kilka bardziej złożonych.

Jeśli naprawdę masz na myśli podzbiór, a więc mówisz o zestawach, a nie listach, możesz po prostu użyć metody subsetOf w Scali. Algorytmy będą zależeć od sposobu przechowywania zestawu. Poniższy algorytm działa dla pamięci listy, która jest bardzo nieoptymalna.

def is_subset[A,B](l1: List[A], l2: List[B]): Boolean = (l1, l2) match { 
    case (_, Nil) => true 
    case (Nil, _) => false 
    case (h1 :: t1, h2 :: t2) if h1 == h2 => is_subset(t1, t2) 
    case (_ :: tail, list) => is_subset(tail, list) 
} 

Answer 11

Dla indexOfSeq w Scala bagażniku I wdrożone KMP, które można zbadać: SequenceTemplate

Answer 12

Oto kilka kompromisów można zrobić. Załóżmy, że masz dwa zestawy elementów, S i T, rysowane z wszechświata U. Chcemy określić, czy S≥T. W jednym z podanych przykładów, mamy

S = {1,2,3,4}
T = {3,4,5}
U = {1,2,3,4,5 }

1. posortowanych list (lub zrównoważone drzewo wyszukiwania)
metody zaproponowanej przez większość plakatów. Jeśli masz już posortowane listy lub nie zależy im na czasie ich tworzenia (powiedzmy, nie robisz tak często), to ten algorytm jest w zasadzie liniowym czasem i przestrzenią. Zazwyczaj jest to najlepsza opcja.

(Żeby być fair w stosunku do innych wyborów tutaj, czas i przestrzeń granice powinny faktycznie zawierają czynniki „Log   | U |” w odpowiednich miejscach, ale zwykle nie jest to relivant)

Struktury danych: Posortowana lista dla każdego z S i T. Albo zbalansowane drzewo wyszukiwania (np. Drzewo AVL, drzewo czerwono-czarne, B +), które może być iterowane w stałej przestrzeni.

Algorytm: Dla każdego elementu w T, poszukaj S liniowo dla tego elementu. Zapamiętaj miejsce, w którym przerwałeś każde wyszukiwanie i rozpocznij następne wyszukiwanie. Jeśli każde wyszukiwanie powiedzie się, to S≥T.

Czas złożoność: około O ( | S | Logowanie | S | + | T | Logowanie | T | ) tworzyć posortowane list, O ( max (| S |, | T |) ) w celu porównania.

przestrzeni złożoność: około O ( | S | + | t | )

Przykład (C++)

#include <set> 
#include <algorithm> 

std::set<int> create_S() 
{ 
    std::set<int> S; 
    // note: std::set will put these in order internally 
    S.insert(3); 
    S.insert(2); 
    S.insert(4); 
    S.insert(1); 
    return S; 
} 

std::set<int> create_T() 
{ 
    std::set<int> T; 
    // note std::set will put these in order internally 
    T.insert(4); 
    T.insert(3); 
    T.insert(5); 
    return T; 
} 

int main() 
{ 
    std::set<int> S=create_S(); 
    std::set<int> T=create_T(); 
    return std::includes(S.begin(),S.end(), T.begin(), T.end()); 
} 

2. Tabele Hash
lepsze średni czas złożoności niż przy posortowanej liście można uzyskać za pomocą tabel mieszających. Ulepszone zachowanie w przypadku dużych zestawów wiąże się z ogólnie niższą wydajnością w przypadku małych zestawów.

Podobnie jak w przypadku list posortowanych, ignoruję złożoność wynikającą z rozmiaru wszechświata.

Struktura danych: Tabela mieszania dla S, wszystko szybko iterowalny T.

algorytmu: Insert każdy element S w swoim hashtable. Następnie dla każdego elementu w T sprawdź, czy znajduje się on w tabeli mieszania.

Czas złożoność: O ( | S | + | T | ) założyć, O ( | T | ) do porównania.

Przestrzeń złożoność: O ( | S | + | T | )

Przykład (C++)

#include <tr1/unordered_set> 

std::tr1::unordered_set<int> create_S() 
{ 
    std::tr1::unordered_set<int> S; 
    S.insert(3); 
    S.insert(2); 
    S.insert(4); 
    S.insert(1); 
    return S; 
} 

std::tr1::unordered_set<int> create_T() 
{ 
    std::tr1::unordered_set<int> T; 
    T.insert(4); 
    T.insert(3); 
    T.insert(5); 
    return T; 
} 

bool includes(const std::tr1::unordered_set<int>& S, 
       const std::tr1::unordered_set<int>& T) 
{ 
    for (std::tr1::unordered_set<int>::const_iterator iter=T.begin(); 
     iter!=T.end(); 
     ++iter) 
    { 
     if (S.find(*iter)==S.end()) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

int main() 
{ 
    std::tr1::unordered_set<int> S=create_S(); 
    std::tr1::unordered_set<int> T=create_T(); 
    return includes(S,T); 
} 

3. Bit ustawia
Jeśli urządzenie wszechświat jest szczególnie mały (załóżmy, że możesz mieć tylko elementy 0-32), wtedy bitset jest rozsądnym rozwiązaniem. Czas działania (ponownie, zakładając, że nie zależy Ci na czasie konfiguracji) jest zasadniczo stały. W przypadku, gdy zależy Ci na konfiguracji, wciąż jest to szybsze niż tworzenie posortowanej listy.

Niestety, zestawy bitowe stają się nieporęczne bardzo szybko nawet w przypadku umiarkowanego rozmiaru wszechświata.

Struktura danych: wektor bitowy (zwykle liczba całkowita) dla każdego z S i T. Możemy kodować S = 11110 i T = 00111 w podanym przykładzie.

Algorytm: Oblicz przecięcia obliczając logicznie i z każdego bitu w S z odpowiedniego bitu T. Jeżeli wynik wynosi T, a następnie S≥T.

Czas złożoność: O ( | U | + | S | + | T | ) do konfiguracji O ( | U | ) do porównania.

przestrzeni złożoność: O ( | U | )

Przykład: (C++)

#include <bitset> 

// bitset universe always starts at 0, so create size 6 bitsets for demonstration. 
// U={0,1,2,3,4,5} 

std::bitset<6> create_S() 
{ 
    std::bitset<6> S; 
    // Note: bitsets don't care about order 
    S.set(3); 
    S.set(2); 
    S.set(4); 
    S.set(1); 
    return S; 
} 

std::bitset<6> create_T() 
{ 
    std::bitset<6> T; 
    // Note: bitsets don't care about order 
    T.set(4); 
    T.set(3); 
    T.set(5); 
    return T; 
} 

int main() 
{ 
    std::bitset<6> S=create_S(); 
    std::bitset<6> T=create_T(); 

    return S & T == T; 
} 

4. Bloom filters
Wszystkie zalety bitsets prędkość , bez brzydkiego ograniczenia rozmiaru wszechświata. Tylko jedna słabsza strona: czasami (często, jeśli nie jesteś ostrożny) dajesz złą odpowiedź: Jeśli algorytm mówi "nie", to zdecydowanie nie masz włączenia. Jeśli algorytm mówi "tak", możesz lub nie. Lepszą dokładność można uzyskać, wybierając duży rozmiar filtra i dobre funkcje skrótu.

Biorąc pod uwagę, że mogą i będą udzielać błędnych odpowiedzi, filtry Blooma mogą brzmieć jak okropny pomysł. Mają jednak określone zastosowania. Zasadniczo można by użyć filtrów Blooma, aby szybko wykonać wiele testów integracji, a następnie użyć wolniej deterministycznej metody, aby zagwarantować poprawność w razie potrzeby. Powiązany artykuł Wikipedii wspomina niektóre aplikacje korzystające z filtrów Bloom.

Struktura danych: A Bloom filter to fantazyjny bitset. Musisz wcześniej wybrać rozmiar filtra i funkcje mieszania.

Algorytm (schemat): Inicjalizacja bitset na 0. Aby dodać element do filtra bloom mieszania go z każdej funkcji mieszającej i ustawić odpowiedni bit w bitset. Określanie włączenia działa tak samo, jak w przypadku zestawów bitowych.

Czas złożoność: O ( rozmiar filtra)

przestrzeni złożoność: O ( rozmiar filtra)

Prawdopodobieństwo poprawności: Zawsze popraw, jeśli odpowiada "S" s nie obejmują T ". Coś takiego jak 0.6185^(| S | x | T |/( filter   rozmiar))) jeśli odpowiada "S zawiera T".W szczególności rozmiar filtra musi być proporcjonalny do iloczynu | S | i | T | dać rozsądne prawdopodobieństwo dokładności.

Answer 13

Możesz zobaczyć problem, aby sprawdzić, czy lista jest podzbiorem innej listy jako ten sam problem, aby sprawdzić, czy podłańcuch należy do łańcucha. Najbardziej znanym algorytmem jest KMP (Knuth-Morris-Pratt). Spójrz na wikipedia dla pseudokodu lub po prostu użyj jakiejś metody String.contains dostępnej w języku twoich preferencji. =)