Strona główna » Algorytmy » Artykuły » Rozłączność Zbiorów
 

Rozłączność Zbiorów

https://mattomatti.com/a0217

Cel

Dane są dwa zbiory liczb. Napisz algorytm, który sprawdzi czy podane zbiory są rozłączne. Postaraj się znaleźć optymalne rozwiązanie, które będzie szybko zwracać odpowiedź. W tym artykule zostaną przedstawione dwa sposoby na rozwiązanie tego problemu.

Przykład

Dany jest zbiór A = {1, 2, 3} oraz B = {4, 5, 6}. Zbiory te nie mają ze sobą ani jednego wspólnego elementu, a więc są rozłączne. Jednak zarówno A jak i zbiór B z zbiorem B = {3} mają dokładnie jeden wspólny element, a więc są nierozłączne.

Implementacja

Rozwiązanie Siłowe

Najmniej optymalnym, ale skutecznym sposobem jest rozwiązanie siłowe. Polega ono na porównaniu każdego elementu zbioru A z każdym elementem zbioru B. W praktyce oznacza to, że jeśli zbiór A ma n elementów, a zbiór B m to złożoność wynosi O(nm) co dla zbiorów o tej samej ilości elementów daje złożoność kwadratową. Oto przykładowa implementacja:

C++C#
Python
  1. def CzyRozlaczne(zbior1, zbior2):
  2.   for x in zbior1:
  3.     for y in zbior2:
  4.       if (x == y):
  5.         return False
  6.   return True

Kod składa się z dwóch zagnieżdżonych pętli w których wykonywane jest porównanie aktualnie wybranych elementów. W przypadku, gdy oba wybrane elementy z różnych zbiorów są sobie równe to algorytm zwraca fałsz. Oznacza to, że zbiory nie są rozłączne.

Rozwiązanie Optymalne

Słabym punktem algorytmu przedstawionego powyżej jest wyszukiwanie elementu z jednego zbioru w drugim przy wkorzystaniu wyszukiwania liniowego. Niestety ze względu na to, że elementy zbioru nie są podane w kolejności rosnącej / malejącej to nie może zostać wykorzystane wyszukiwanie binarne. Dane jednak zawsze można wpierw posortować w jednej tablicy i dopiero wykonywać wyszukiwanie. Jednak czy jest to najbardziej optymalne rozwiązanie? Jak wiadomo sortowanie też potrzebuje trochę czasu...

Jeden z pomysłów, który nie wymaga sortowania i jest w stanie porównać zbiory w rozsądnym czasie, jest wykorzystanie hashowania. Oczywiście skuteczność takiego rozwiązania będzie zależeć od tego jak dobrze funkcja hashująca porozdziela dane.

C++C#
Python
  1. def CzyRozlaczne(zbior1, zbior2):
  2.   hashmap = {}
  3.   klucz = -1
  4.   for x in zbior1:
  5.     klucz = Klucz(x);
  6.     if (not klucz in hashmap):
  7.       hashmap[klucz] = []
  8.     hashmap[klucz].append(x)
  9.   for y in zbior2:
  10.     klucz = Klucz(y)
  11.     if (klucz in hashmap):
  12.       if (y in hashmap[klucz]):
  13.         return False
  14.   return True

Algorytm ponownie składa się z dwóch pętli, ale tym razem w pierwszej jest tworzona mapa hashy na podstawie zbioru 1, a następnie elementy zbioru 2 są wyszukiwane w mapie. Jeśli żaden klucz nie zawiera kolejnej liczby z zbioru 2 to należy zwrócić prawdę czyli, że zbiory są rozłączne. Oto przykładowa funkcja hashująca dane:

C++C#
Python
  1. def Klucz(a):
  2.   return a % 100

Powyższa funkcja zakłada, że liczby są rozmieszczone równomiernie między maskimum, a minimum.

Testowanie funkcji

Poniższy fragment kodu wczytuje dwa zbiory liczb, a następnie wypisuje komunikat czy są one rozłączne.

C++C#
Python
  1. print("- Zbiór 1 -\nPodaj liczby:")
  2. zbior1 = [int(x) for x in input().split()]
  3. print("- Zbiór 2 -\nPodaj liczby:")
  4. zbior2 = [int(x) for x in input().split()]
  5. wynik = CzyRozlaczne(zbior1, zbior2)
  6. if (wynik):
  7.   print("Zbiory są rozłączne")
  8. else:
  9.   print("Zbiory mają przynajmniej 1 wspólny element")