Inverse Permutations and Ordering

Staff Picks
, , ,
1

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[1]:= Range[10] -> (perm = RandomSample[Range[10]])

  Out[1]= {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[2]:= foo = Part[Array[a, 10], perm]
  %[[All, 1]] == perm

  Out[2]= {a[4], a[5], a[2], a[7], a[6], a[3], a[10], a[9], a[1], a[8]}

  Out[3]= True

Inverse Permutations and Ordering

  • The inverse permutation reverses the arrow:

      In[4]:= perm -> Range[10]
  
  Out[4]= {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[5]:= ord = Ordering[perm];

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

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

 Out[6]= True

 In[7]:= sort = Part[foo, ord]

 Out[7]= {a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10]}

 In[8]:= sort == Sort[foo]

 Out[8]= 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[9]:= perm1 = RandomSample[Range[10]];
          perm2 = RandomSample[Range[10]];
  
  In[11]:= Part[Part[Array[a, 10], perm1], perm2] == Part[Array[a, 10], Part[perm1, perm2]]
  
  Out[11]= True

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

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

  Out[12]= True

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

      In[13]:= n = 10^6;
  arr = Array[a, n];
  perm = RandomSample[Range[n]];
  
  In[16]:= Fold[Part, ConstantArray[perm, 6]]; // RepeatedTiming
  
  Out[16]= {0.2, Null}
  
  In[17]:= (foo = Part[arr, Fold[Part, ConstantArray[perm, 6]]];) // RepeatedTiming
  
  Out[17]= {0.459, Null}
  
  In[18]:= (bar = Fold[Part, arr, ConstantArray[perm, 6]];) // RepeatedTiming
  
  Out[18]= {1.9479, Null}
  
  In[19]:= foo == bar
  
  Out[19]= 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[20]:= arr = Array[a, 10];
  ord = Ordering[arr];
  sort = Part[arr, ord];
  
  In[23]:= Part[sort, Ordering[ord] ] == arr
  
  Out[23]= True

2 Argument Ordering

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

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

  Out[2]= {a[5]}

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

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

  Out[3]= 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[1]:= foo = Prepend[Range[0, 10, 2], 5]

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

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

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

  Out[3]= {4}

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

  Out[4]= {{4}}

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

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

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

  In[6]:= Quantile[bar, 5/10]

  Out[6]= 4

  In[7]:= Quantile[bar, 4/10]

  Out[7]= 4

  In[8]:= Quantile[bar, 2/10]

  Out[8]= 2
2 Likes
2

2015-11-02_10-07-11.png

  • Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!