Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ToInversionVector

Source Notebook

Get the inversion vector of a permutation written as a list

Contributed by: Wolfram Staff

ResourceFunction["ToInversionVector"][p]

gives the inversion vector of the permutation list p.

Details and Options

The inversion vector of a permutation of length n lists the number of times k is preceded by an entry greater than k, where k runs from 1 to n.

Examples

Basic Examples (2) 

This permutation has 3 numbers greater than 1 before 1, 2 numbers greater than 2 before 2, and so on:

In[1]:=
p1 = {4, 3, 2, 1};

Therefore, this is its inversion vector:

In[2]:=
ResourceFunction["ToInversionVector"]@p1
Out[2]=

Here is another example:

In[3]:=
p2 = PermutationList@RandomPermutation@12
Out[3]=
In[4]:=
ResourceFunction["ToInversionVector"]@p2
Out[4]=

Scope (3) 

Here are all six permutation of {1,2,3}:

In[5]:=
s3 = Permutations@{1, 2, 3}
Out[5]=

Here are the corresponding inversion vectors:

In[6]:=
ivs = ResourceFunction["ToInversionVector"] /@ s3
Out[6]=

In the factorial base, ivs represents the numbers from 0 to 3!-1:

In[7]:=
FromDigits[#, MixedRadix[{3, 2, 1}]] & /@ ivs
Out[7]=

Publisher

George Beck

Version History

  • 1.0.0 – 31 May 2019

Related Resources

Author Notes

The Combinatorica` function ToInversionVector did not include the final zero.

License Information