Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ordering@Ordering and Ranking Permutations

As pointed out by nazdrovje (see here) Ordering@Ordering may be used to obtain the rank of each element in a list. Even when the list contains repeated elements the result is an n-permutation (taken as an ordered list of integers 1 to n without repetition), where the lowest ranked element is assigned 1, the second lowest 2, etc. As pointed out by Andrzej Kozlowski, the following holds (see also here):

(Sort@mylist)[[Ordering@Ordering@mylist]]==mylist

I'd like to produce a ranking permutation where the highest ranked element is assigned 1, the second highest 2, etc. such that the following holds:

(Reverse@Sort@mylist)[[newPermutation]]==mylist

This seems simple, but I have only been able to come up with quite an awkward solution. At the moment I do the following:

newPermutation= Ordering@Ordering[Ordering@Ordering@mylist,All,Greater]

Is there a more elegant,or more intuitive, way? There surely must be?

An example:

mylist= {\[Pi],"abc",40,1, 300, 3.2,1};

Ordering@Ordering@mylist

Ordering@Ordering[Ordering@Ordering@mylist,All,Greater]

Output (note the reciprocal relationship between the permutations)

{7,6,4,1,5,3,2}
{1,2,4,7,3,5,6}

(Both the following evaluate to True)

Sort@mylist)[[Ordering@Ordering@mylist]]== mylist
Reverse@Sort@mylist)[[ Ordering@Ordering[Ordering@Ordering@mylist,All,Greater]]]== mylist
like image 993
681234 Avatar asked Jan 20 '11 01:01

681234


People also ask

Is ranking a permutation?

A ranking function is called lexicographic if it maps a permutation and its lexicographi- cally next permutation into consecutive integers. There are well-known algorithms for these tasks that per- form O(n) arithmetic operations but not in lexicographic order (Myrvold & Ruskey 2001).


1 Answers

If you set

 oldPerm = Ordering@Ordering@mylist

then

 newPerm = - oldPerm + Length@mylist + 1

and

(Reverse@Sort@mylist)[[newPerm]]==mylist

is True


So, you may define

newPerm[x_] := 1 + Length@x - Ordering@Ordering@x

Such as

(Reverse@Sort@mylist)[[newPerm[mylist]]] == mylist  

is True

like image 109
Dr. belisarius Avatar answered Oct 03 '22 09:10

Dr. belisarius