Unikalne Pary

Zadanie

Dana jest lista liczb całkowitych dla której trzeba znaleźć ile unikalnych par można z nich uzyskać. Zakładamy, że kolejność liczb w parze ma znaczenie, a więc (a, b) jest różne od (b, a).

Przykład

Przypuśćmy, że dana jest tablica {1, 2, 1}. Możliwe unikalne pary do uzyskania to {(1, 1), (1, 2), (2, 1), (2, 2)}, a więc program powinien zwrócić 4 tj. liczbę uzyskanych różnych par liczb.

Implementacja

Rozwiązanie Siłowe

Najprostsze rozwiązanie polega na przejrzeniu wszystkich możliwych par i wrzucanie ich do zbioru. Na koniec zwracany jest rozmiar zbioru, który z definicji nie posiada dwóch identycznych wartości. Charakteryzuje je kwadratowa złożoność czasowa i pamięciowa O(n²). Oznacza to, że algorytm będzie działał długo i zużywał dużo pamięci. Oto przykładowy kod:

1. int IleUnikalnychPar(vector<int> lista) {
2.   set<pair<int, int>> zbior;
3.   for (int i = 0; i < lista.size(); i++) {
4.     for (int j = 0; j < lista.size(); j++) {
5.       zbior.insert(make_pair(lista[i], lista[j]));
6.     }
7.   }
8.   return zbior.size();
9. }

Na początku deklarowany jest zbiór par, a następnie w podwójnej pętli generowane są wszystkie możliwe pary, a na koniec zwracany jest rozmiar uzyskanego zbioru.

Rozwiązanie Optymalne

Poprzedni algorytm można poprawić ze względu na czas działania jak i na zużycie pamięci. Po pierwsze warto zauważyć, że dla n unikalnych wartości istnieje dokładnie n² par. W celu wyznaczenia unikalnych wartości sortujemy dane, a potem zliczamy ile jest unikalnych wartości. Wynikiem działania funkcji będzie kwadrat licznika. Złożoność czasowa takiego algorytmu zależy od wybranego algorytmu sortowania np. O(n·logn). Złożoność pamięciowa może być O(1) jeśli algorytm będzie sortować w miejscu. To znacznie lepszy wynik niż w rozwiązaniu siłowym.

1. int IleUnikalnychPar(vector<int> lista) {
2.   sort(lista.begin(), lista.end());
3.   int poprz = lista[0];
4.   int unikalnych = 1;
5.   for (int i = 1; i < lista.size(); i++) {
6.     if (lista[i] != poprz) {
7.       unikalnych++;
8.       poprz = lista[i];
9.     }
10.   }
11.   return unikalnych * unikalnych;
12. }

Algorytm sortuje dane, a następnie inicjalizuje licznik na wartość 1 i porównuje kolejne pary elementów w posortowanej tablicy. Jeśli wartości są różne to licznik zostaje zwiększony. Na koniec zwracany jest kwadrat obliczonego licznika.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu, który wczyta od użytkownika listę liczb, a następnie wypisze ile unikalnych liczb można uzyskać.

1. int main () {
2.   int n, tmp;
3.   cout << "Ile liczb?\n n = ";
4.   cin >> n;
5.   cout << "Podaj liczby:\n";
6.   vector<int> lista;
7.   while (n--) {
8.     cin >> tmp;
9.     lista.push_back(tmp);
10.   }
11.   int wynik = IleUnikalnychPar(lista);
12.   cout << "Unikalnych par: " << wynik;
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja