Message Boards Message Boards

Inverse Permutations and Ordering

Posted 6 years ago

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

  • Orderingalso 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
    
POSTED BY: Eduardo Serna

enter image description here - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!

POSTED BY: Moderation Team
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract