Strona główna » Algorytmy » Artykuły » Zliczanie Inwersji
 

Zliczanie Inwersji

Inwersja

Definicja

Inwersja jest to para liczb ai, aj w ciągu a1, a2, .., an, gdzie i < j, a aj > ai. 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ą:

Indeks i111223
Indeks j234344
Porównanie3 < 43 > 13 > 24 > 14 > 23 < 4
Czy inwersja?NieTakTakTakTakNie

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:

Indeks i111223
Indeks j234344
Porównanie1 < 21 < 31 < 42 < 32 < 43 < 4
Czy inwersja?NieNieNieNieNieNie

Łą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:

Indeks i111223
Indeks j234344
Porównanie4 > 34 > 24 > 13 > 23 > 12 > 1
Czy inwersja?TakTakTakTakTakTak

Łą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 a1, a2, .., an przestawienie an na pierwszą pozycję powoduje zwiększenie liczby inwersji o n - 1, przedstawiając element an - 1 na drugą pozycję zwiększymy o n - 2. Powtarzając ten proces otrzymamy ciąg posortowany odwrotnie an, an - 1, .., a1. Każdy element dodaje maksymalną liczbę inwersji jaką może utworzyć. Wtedy imax(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 n2, a że operacja porównania jest operacją dominującą to algorytm będzie miał złożoność O(n2).

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 a1, a2, .., an, gdzie ai jest liczbą całkowitą.

C++
C#
  1. static int zliczInwersje(int[] tab) {
  2.   int inwersji = 0;
  3.   for (int i = 0; i < tab.Length - 1; i++) {
  4.     for (int j = i + 1; j < tab.Length; 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.

C++
C#
  1. static void Main(string[] args) {
  2.   Console.Write("Ile liczb ma tablica?\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   int[] tab = new int[n];
  5.   Console.WriteLine("Podaj elementy tablicy:");
  6.   for (int i = 0; i < n; i++)
  7.     tab[i] = Convert.ToInt32(Console.ReadLine());
  8.   int ile = zliczInwersje(tab);
  9.   Console.WriteLine("Inwersji: {0}", ile);
  10.   Console.ReadKey();
  11. }
Zadania
Zadanie 1
Napisz program, który wczyta dwie listy identycznej długości, a następnie zliczy liczbę inwersji drugiej tablicy względem pierwszej. Innymi słowy porównaj jak podobne są obydwie tablice. Wskazówka: tym razem nie będa porównywane wartości indeksów tablicy i oraz j, a pozycje tych wartości w pierwszej tablicy.
Przykład
Weźmy dwie permutacje {7, 5, 3, 4} oraz {3, 5, 4, 7}. Oznaczmy przez w(x) funkcję, która będzie zwracać indeks elementu x w tablicy pierwszej. Wtedy rozpisanie wygląda następująco:
#Indeks i111223#Indeks j234344#Elementyw(1) ? w(2)w(1) ? w(3)w(1) ? w(4)w(2) ? w(3)w(2) ? w(4)w(3) ? w(4)#Porównanie7 > 57 > 37 > 45 > 35 > 43 < 4#Czy inwersja?TakTakTakTakTakNie
Podsumowując wynikiem działania funkcji dla tablic {7, 5, 3, 4} oraz {3, 5, 4, 7} jest:
5
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1