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:

  1. bool CzyRozlaczne(vector<int> zbior1, vector<int> zbior2) {
  2.   for (int i = 0; i < zbior1.size(); i++) {
  3.     for (int j = 0; j < zbior2.size(); j++) {
  4.       if (zbior1[i] == zbior2[j]) {
  5.         return false;
  6.       }
  7.     }
  8.   }
  9.   return true;
  10. }

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.

  1. bool CzyRozlaczne(vector<int> zbior1, vector<int> zbior2) {
  2.   map<int, vector<int>> hashmap;
  3.   map<int, vector<int>>::iterator it;
  4.   for (int i = 0; i < zbior1.size(); i++) {
  5.     it = hashmap.find(Klucz(zbior1[i]));
  6.     if (it == hashmap.end()) {
  7.       hashmap.insert(make_pair(Klucz(zbior1[i]), vector<int>()));
  8.       it = hashmap.find(Klucz(zbior1[i]));
  9.     }
  10.     it->second.push_back(zbior1[i]);
  11.   }
  12.   for (int j = 0; j < zbior2.size(); j++) {
  13.     it = hashmap.find(Klucz(zbior2[j]));
  14.     if (it != hashmap.end()) {
  15.       for each (int x in it->second)
  16.       {
  17.         if (x == zbior2[j]) {
  18.           return false;
  19.         }
  20.       }
  21.     }
  22.   }
  23.   return true;
  24. }

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:

  1. int Klucz(int a) {
  2.   return a % 100;
  3. }

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.

  1. vector<int> WczytajLiczby() {
  2.   int n, tmp;
  3.   vector<int> liczby;
  4.   cout << "Ile liczb?\n n = ";
  5.   cin >> n;
  6.   while (n-- > 0) {
  7.     cin >> tmp;
  8.     liczby.push_back(tmp);
  9.   }
  10.   return liczby;
  11. }
  13. int main () {
  14.   cout << "- Zbior 1 -" << endl;
  15.   vector<int> zbior1 = WczytajLiczby();
  16.   cout << "- Zbior 2 -" << endl;
  17.   vector<int> zbior2 = WczytajLiczby();
  18.   bool wynik = CzyRozlaczne(zbior1, zbior2);
  19.   if (wynik) {
  20.     cout << "Zbiory sa rozlaczne";
  21.   } else {
  22.     cout << "Zbiory maja przynajmniej 1 wspolny element";
  23.   }
  24.   system("pause");
  25.   return 0;
  26. }