Zliczanie Inwersji

Inwersja

Definicja

Inwersja jest to para liczb a_i, a_j w ciągu a₁, a₂, .., a_n, gdzie i < j, a a_j > a_i. W matematycę funkcję zliczania inwersji oznaczamy i(X), gdzie X to pewna permutacja ciągu. Jako liczbę inwersji uznajemy łączą ilość inwersji dla danej permutacji.

Zastosowanie

Łączna liczba inwersji pokazuje jak tablica jest daleko od bycia posortowaną. Warto tutaj zaznaczyć, że ciąg posortowany ma liczbę inwersji 0, a ciąg posortowany odwrotnie maksymalną wartość iwnersji. Poza tym liczenie inwersji dla dwóch dowolnych tablic może powiedzieć jak bardzo podobne są obydwie tablice.

Przykłady

Pewna Permutacja

Weźmy ciąg (1, 2, 3, 4) i utwórzmy jego permutacje: (3, 4, 1, 2). W celu zliczenia liczby inwersji należy teraz porównać każdą parę liczb o różnych indeksach i zliczyć ile razy większa liczba występuje przed mniejszą:

Zliczając ilość otrzymanych inwersji otrzymujemy 4. Oznacza to, że 4 z 6 par nie są ustawione w sposób rosnący.

Posortowana Permutacja

Tym razem rozpatrzmy ciąg posortowany (1, 2, 3, 4). Wtedy otrzymujemy:

Łączna liczba inwersji to 0. Niezależnie od długości wybranego ciągu jeśli jest on posortowany to liczba inwersji wynosi dokładnie 0. Można to udowodnić następująco: niezależnie od wybranego indeksu i nie istnieje taki indeks j, aby wartość i indeksie j była mniejsza od tej na pozycji i.

Posortowana Permutacja Odwrotnie

Tym razem rozpatrzmy permutację (4, 3, 2, 1), która w myśl inwersji jest najdalej od posortowanej. Rozpisując tabelkę otrzymujemy:

Łączna liczba inwersji to 6. Otrzymaliśmy maksymalną liczbę inwersji dla ciągu czteroelementowego. Dla ciągu o innej długości maksymalna liczba jest inna.

Maksymalna Liczba Inwersji

Zauważmy, że w ciągu liczb a₁, a₂, .., a_n przestawienie a_n na pierwszą pozycję powoduje zwiększenie liczby inwersji o n - 1, przedstawiając element a_{n - 1} na drugą pozycję zwiększymy o n - 2. Powtarzając ten proces otrzymamy ciąg posortowany odwrotnie a_n, a_{n - 1}, .., a₁. Każdy element dodaje maksymalną liczbę inwersji jaką może utworzyć. Wtedy i_max(X) = (n - 1) + (n - 2) + .. + 1 + 0 = n·(n - 1)/2 co wynika z sumy na ciąg arytmetyczny wyrazów od 0 do n - 1.

Implementacja

Chcą napisać program, który w naiwny sposób zlicza łączną liczbę inwersji pewnej permutacji jest bardzo podobny do sortowania bąbelkowego: porównujemy każdą możliwą parę elementów i jeśli istnieje potrzeba ich zamiany to zwiększamy licznik inwersji. Ze względu na fakt, że porównujemy każdą liczbę z każdą to łączna liczba porównań wyniesie n², a że operacja porównania jest operacją dominującą to algorytm będzie miał złożoność O(n²).

Oto kod funkcji zliczającej inwersje zliczInwersje(), która na podstawie przekazanej tablicy tab sprawdza ile występuje inwersji. Uwaga: Algorytm zakłada, że dla tablicy długości n ciągiem wyjściowym jest a₁, a₂, .., a_n, gdzie a_i jest liczbą całkowitą.

1. int zliczInwersje(int* tab, int n) {
2.   int inwersji = 0;
3.   for (int i = 0; i < n - 1; i++) {
4.     for (int j = i + 1; j < n; j++) {
5.       if (tab[i] > tab[j]) {
6.         inwersji++;
7.       }
8.     }
9.   }
10.   return inwersji;
11. }

(2.) Inicjalizacja licznika. Następnie (3. - 4.) wybór indeksu i i j. Potem jeśli (5.) jest inwersja to (6.) zwiększamy licznik. Na koniec (9.) zwracamy łączną liczbę inwersji.

Nie jest to jednak najszybszy możliwy algorytm wyznaczania liczby inwersji. Istnieje szybszy, który opiera się na Sortowaniu Przez Scalanie.

Testowanie funkcji

Poniższy kod wczytuje od użytkownika tablicę liczb tab o pewnej długości n i pokazuje ile inwersji występuje w ciągu.

1. int main() {
2.   int n;
3.   cout << "Ile liczb ma tablica?\n n = ";
4.   cin >> n;
5.   int* tab = new int[n];
6.   cout << "Podaj elementy tablicy:" << endl;
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   int ile = zliczInwersje(tab, n);
10.   cout << "Inwersji: " << ile;
11.   system("pause");
12.   return 0;
13. }

• Kod źródłowy Implementacja