informacja o liczbie cyfr znajdujących się na lewo od n-tego miejsca większych od liczby na n-tym miejscu w permutacji. Za jego pomocą jednoznacznie można zakodować dany ciąg.
· Zaczynając od prawej strony sprawdzać ile liczb jest większych na lewo od badanej liczby.
· Zapisać podane wartości jako ciąg.
Przykład:
Permutacja
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Nr pozycji
|
9
|
8
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
Liczby większe na lewo od tego miejsca
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
Wektor
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
123456789 daje nam po zakodowaniu 000000000
Permutacja
|
9
|
5
|
7
|
8
|
6
|
4
|
1
|
2
|
3
|
Nr pozycji
|
9
|
8
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
Liczby większe na lewo od tego miejsca
|
-
|
9
|
9
|
9
|
7, 8, 9
|
5, 6, 7, 8, 9
|
4, 5, 6, 7, 8, 9
|
4, 5, 6, 7, 8, 9
|
4, 5, 6, 7, 8, 9
|
Wektor
|
0
|
1
|
1
|
1
|
3
|
5
|
6
|
6
|
6
|
957864123 daje nam po zakodowaniu 011135666
Jak sprawdzić czy ciąg liczb jest
wektorem jakiejś permutacji?
· Na n-tym miejscu cyfra może być mniejsza lub równa l-n, gdzie l jest liczbą cyfr
wektora.
Przykład: l=4,
Nr pozycji (n)
|
4
|
3
|
2
|
1
|
Wektor
|
0
|
2
|
0
|
0
|
l-n
|
0
|
1
|
2
|
3
|
Czy l-n jest większe lub równe cyfrze na n-tej pozycji
|
Tak
|
Nie
|
Tak
|
Tak
|
A
zatem ten ciąg nie jest wektorem inwersji. Przed liczbą na pozycji nr 3 nie
mogą stać dwie cyfry większe od cyfry na n-tym miejscu, bo na lewo jest tylko
jedna cyfra.
Przykład: l=7
Nr pozycji (n)
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
Wektor
|
0
|
0
|
1
|
0
|
2
|
0
|
4
|
l-n
|
0
|
1
|
2
|
3
|
5
|
6
|
7
|
Czy l-n jest większe lub równe cyfrze na n-tej pozycji
|
Tak
|
Tak
|
Tak
|
Tak
|
Tak
|
Tak
|
Tak
|
A
zatem ten ciąg jest wektorem inwersji.
Jak odkodować wektor?
· Sprawdzamy długość ciągu. Uzyskujemy wtedy informację o tym, iluelementowego zbioru permutacja została zakodowana. Następnie działamy na zbiorze kolejnych n liczb naturalnych.
· Zaczynamy dekodować od pierwszej z prawej pozycji. Wiemy, że jeśli na tej pozycji stoi liczba k, to na lewo od niej jest dokładnie k liczb większych od tej z tego miejsca w permutacji. A zatem wybieramy k+1-szą największą liczbę ze zbioru liczb naturalnych określonego w pierwszym kroku
· Następnie usuwamy tę liczbę ze zbioru i zapisujemy ją na l-k-tym miejscu.
· Postępujemy tak z każda liczbą w wektorze.
· Zaczynamy dekodować od pierwszej z prawej pozycji. Wiemy, że jeśli na tej pozycji stoi liczba k, to na lewo od niej jest dokładnie k liczb większych od tej z tego miejsca w permutacji. A zatem wybieramy k+1-szą największą liczbę ze zbioru liczb naturalnych określonego w pierwszym kroku
· Następnie usuwamy tę liczbę ze zbioru i zapisujemy ją na l-k-tym miejscu.
· Postępujemy tak z każda liczbą w wektorze.
Przykład
Wektor
|
Zbiór liczb
|
Permutacja
|
0010204
|
1, 2, 3, 4, 5, 6, 7 piąta największa liczba – wykreślamy ją
|
XXXXXX3
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
XXXXX73
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
XXXX473
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
XXX6473
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
XX26473
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
X526473
|
0010204
|
1, 2, 3, 4, 5, 6, 7
|
1526473
|