Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 InversionVectorQ

Source Notebook

Check if a list is the inversion vector of a permutation written as a list

Contributed by: Wolfram Staff

ResourceFunction["InversionVectorQ"][iv]

checks if iv is the inversion vector of a permutation list.

Details and Options

The inversion vector of a permutation of length n lists the number of times k is preceded by a number greater than k, where k runs from 1 to n.
The definition amounts to checking whether the entries of the vector are the digits of a number in base-factorial.

Examples

Basic Examples (2) 

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

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

Therefore this is its inversion vector:

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

Here is a check:

In[3]:=
ResourceFunction["InversionVectorQ"][{3, 2, 1, 0}]
Out[3]=

The positive integer 23 gives {3,2,1,0} in the factorial base, so {3,2,1,0} is an inversion vector:

In[4]:=
IntegerDigits[23, MixedRadix[{4, 3, 2, 1}]]
Out[4]=

Every inversion vector must end in 0 because the largest entry in a permutation list has nothing but smaller entries before it:

In[5]:=
ResourceFunction["InversionVectorQ"][{0, 1, 2, 3}]
Out[5]=

Publisher

George Beck

Version History

  • 1.0.0 – 23 May 2019

Related Resources

License Information