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. static bool CzyRozlaczne(int[] zbior1, int[] zbior2) {
  2.   for (int i = 0; i < zbior1.Length; i++) {
  3.     for (int j = 0; j < zbior2.Length; 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. static bool CzyRozlaczne(int[] zbior1, int[] zbior2) {
  2.   Dictionary<int, List<int>> hashmap = new Dictionary<int, List<int>>();
  3.   int klucz = -1;
  4.   foreach(int x in zbior1) {
  5.     klucz = Klucz(x);
  6.     if (!hashmap.ContainsKey(klucz)) {
  7.       hashmap.Add(klucz, new List<int>());
  8.     }
  9.     hashmap[klucz].Add(x);
  10.   }
  11.   foreach (int y in zbior2) {
  12.     klucz = Klucz(y);
  13.     if (hashmap.ContainsKey(klucz)) {
  14.       if (hashmap[klucz].Contains(y)) {
  15.         return false;
  16.       }
  17.     }
  18.   }
  19.   return true;
  20. }

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. static 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. static int[] WczytajLiczby() {
  2.   string[] dane = Console.ReadLine().Split(' ');
  3.   int[] liczby = new int[dane.Length];
  4.   for(int i = 0; i < dane.Length; i++) {
  5.     liczby[i] = Convert.ToInt32(dane[i]);
  6.   }
  7.   return liczby;
  8. }
  10. static void Main(string[] args) {
  11.   Console.WriteLine("- Zbiór 1 -\nPodaj liczby:");
  12.   int[] zbior1 = WczytajLiczby();
  13.   Console.WriteLine("- Zbiór 2 -\nPodaj liczby:");
  14.   int[] zbior2 = WczytajLiczby();
  15.   bool wynik = CzyRozlaczne(zbior1, zbior2);
  16.   if (wynik) {
  17.     Console.WriteLine("Zbiory są rozłączne");
  18.   } else {
  19.     Console.WriteLine("Zbiory mają przynajmniej 1 wspólny element");
  20.   }
  21.   Console.ReadKey();
  22. }