From inversion back to permutation...
Posted: Wed Nov 17, 2004 9:30 pm
I would like to ask for fast algorithm for getting back from inversion to permutation. Inversion is a pair of indexes {i,j} make an inversion when (i<j) AND (Ai>Aj), and I would like to find the permutation from which inversion has been created:
For example:
Input: 0 0 1 2 1 1 5 6
Output: 1 8 5 4 6 7 3 2 (or any other proper permutation if such exists - what I don't know - is there only one proper inversion for each permutation???)
PLEASE HELP!!!!
For example:
Input: 0 0 1 2 1 1 5 6
Output: 1 8 5 4 6 7 3 2 (or any other proper permutation if such exists - what I don't know - is there only one proper inversion for each permutation???)
PLEASE HELP!!!!