# Inverse Permutations and Ordering

Posted 10 months ago
993 Views
|
1 Reply
|
2 Total Likes
|

This is my first community post, and it is a cleaned up version of a notebook I did for myself after having to find an inverse permutation (which is mentioned in the documentation for Ordering but only in passing).

## Permutations and Part

• A permutation is a mapping (bijection, i.e. invertible) between positions in an ordered set:

i -> j

• For example, giving the elements to the left of the permutation in sorted form:

In:= Range -> (perm = RandomSample[Range])

Out= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} -> {4, 5, 2, 7, 6, 3, 10, 9, 1, 8}

• This permutation can be implemented with Part:

In:= foo = Part[Array[a, 10], perm]
%[[All, 1]] == perm

Out= {a, a, a, a, a, a, a, a, a, a}

Out= True


## Inverse Permutations and Ordering

• The inverse permutation reverses the arrow:

In:= perm -> Range

Out= {4, 2, 5, 1, 10, 8, 6, 3, 9, 7} -> {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

• To use part we must rearrange the specification so that the list on the left is sorted. We need to find the permutation which sorts the list on the left, so we can apply it to the list on the right.

• Ordering gives the permutation that sorts a list:

In:= ord = Ordering[perm];

• Because the list on the right is already sorted this permutation is the inverse permutation we are looking for:

In:= Part[Range, ord] == ord

Out= True

In:= sort = Part[foo, ord]

Out= {a, a, a, a, a, a, a, a, a, a}

In:= sort == Sort[foo]

Out= True


## Functional compositions of permutations

• Composition of permutations is associative because functional composition is:

• The composition of two permutations can be expressed as applying one permutation on the other:

    i -> j -> k ===> i -> k

In:= perm1 = RandomSample[Range];
perm2 = RandomSample[Range];

In:= Part[Part[Array[a, 10], perm1], perm2] == Part[Array[a, 10], Part[perm1, perm2]]

Out= True

• From this follows that applying the inverse permutation to the permutation itself should give us the identity permutation:

In:= Part[perm, ord] == Part[ord, perm] == Range

Out= True

• Associativity is also important because permutations themselves can be PackedArrays so choosing to operate on PackedArrays can be much faster:

In:= n = 10^6;
arr = Array[a, n];
perm = RandomSample[Range[n]];

In:= Fold[Part, ConstantArray[perm, 6]]; // RepeatedTiming

Out= {0.2, Null}

In:= (foo = Part[arr, Fold[Part, ConstantArray[perm, 6]]];) // RepeatedTiming

Out= {0.459, Null}

In:= (bar = Fold[Part, arr, ConstantArray[perm, 6]];) // RepeatedTiming

Out= {1.9479, Null}

In:= foo == bar

Out= True


## Undoing a sort operation

• Say we have the Ordering, and the sorted list, we can recover the original list with another Ordering operation:

In:= arr = Array[a, 10];
ord = Ordering[arr];
sort = Part[arr, ord];

In:= Part[sort, Ordering[ord] ] == arr

Out= True


## 2 Argument Ordering

• Orderingalso allows us to get the nth element in the sorted list, efficiently:

In:= arr = RandomSample[Array[a, 10]];
Part[arr, Ordering[arr, {5}]]

Out= {a}

• If the list is numeric, we can use RankedMin:

In:= RankedMin[RandomSample[Range], 5]

Out= 5


## Quantiles and Ordering

• A related problem is finding the position in the sorted list, of the nth element in the original list, efficiently:

In:= foo = Prepend[Range[0, 10, 2], 5]

Out= {5, 0, 2, 4, 6, 8, 10}

• It requires two Ordering operations, but one is partial:

In:= ord = Ordering[foo];
pos = Ordering[ord, 1]

Out= {4}

In:= Position[Sort[foo], 5]

Out= {{4}}

• Quantile of a list does a similar thing, but one has to be careful with ties:

In:= bar = Range[0, 10, 2]

Out= {0, 2, 4, 6, 8, 10}

In:= Quantile[bar, 5/10]

Out= 4

In:= Quantile[bar, 4/10]

Out= 4

In:= Quantile[bar, 2/10]

Out= 2 Answer
1 Reply
Sort By:
Posted 10 months ago - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming! Answer
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments