[Algorytmy] Przekształcenie wektora inwersji permutacji

Rjiuk
Użytkownik
Użytkownik
Posty: 22
Rejestracja: 6 sty 2012, o 13:50
Płeć: Mężczyzna
Lokalizacja: Mszczonów
Podziękował: 1 raz
Pomógł: 1 raz

[Algorytmy] Przekształcenie wektora inwersji permutacji

Post autor: Rjiuk »

Witam , muszę znaleźć sposób na przekształcenie wektora inwersji permutacji w orginalny ciąg przy pomocy drzewa przedziałowego. Potrzebuje jakiegoś hinta , wskazówki, zupełnie nie mam pomysłu na to .

Dziękuję za wszystkie sensowne odpowiedzi -- 29 cze 2012, o 13:30 --A więc rozwiązałem już problem, napisze pewne wskazówki dla tych którzy kiedyś będą jeszcze mieli podobny problem.

Algorytm będzie konstruował oryginalny ciąg "od końca" czyli najpierw ostatni element, potem przedostatni itp. Spróbuj odpowiedzieć na następujące 3 pytania:

1) Jak mając dany wektor inwersji wyznaczyć ostatni element ciągu oryginalnego?

2) Załóżmy że udało Ci się obliczyć pewien sufiks ciągu oryginalnego, i chcesz policzyć kolejny element w kolejności "od końca". Załóżmy też że przechowujesz jakoś informacje o zbiorze liczb których jeszcze nie użyłeś. Którą liczbę z tego zbioru chcesz teraz użyć?

3) Jak użyć drzewa przedziałowego tak, by efektywnie przechowywać informacje o zbiorze liczb jeszcze nie użytych i w kolejnych krokach szybko uzyskać liczbę której szukasz?
Ostatnio zmieniony 27 cze 2012, o 17:25 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
ODPOWIEDZ