close

Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationIndex

Source Notebook

Give the lexicographic index of a permutation

Contributed by: Ed Pegg Jr

ResourceFunction["PermutationIndex"][perm]

gives the lexicographic index of permutation perm.

Details and Options

Permutations are considered to be in normal sorted order.
Lehmer codes are generated as an intermediary step.
The generating algorithm for Lehmer codes is as follows: For each number in the permutation, count how many subsequent values it exceeds.

Examples

Basic Examples (2) 

Return the index of a permutation:

In[1]:=
ResourceFunction["PermutationIndex"][{4, 3, 2, 1}]
Out[1]=
Image

The first permutation of a given length has index 1:

In[2]:=
ResourceFunction["PermutationIndex"][{1, 2, 3, 4, 5, 6, 7}]
Out[2]=
Image

Scope (4) 

Some large permutations:

In[3]:=
large = Table[RandomSample[Range[20]], {4}]
Out[3]=
Image

Large permutations can be indexed:

In[4]:=
lr = ResourceFunction["PermutationIndex"] /@ large
Out[4]=
Image

Terms don’t necessarily need to be positive or integer:

In[5]:=
lrn = ResourceFunction["PermutationIndex"] /@ (-large + 1/2)
Out[5]=
Image

The indices of permutations and negative permutations are balanced:

In[6]:=
lr + lrn - 1 - 20!
Out[6]=
Image

Neat Examples (1) 

Differences of indices of even permutations:

In[7]:=
Differences[ ResourceFunction["PermutationIndex"] /@ GatherBy[Permutations[Range[5]], Signature][[1]]]
Out[7]=
Image

Version History

  • 1.0.0 – 20 December 2019

Related Resources

License Information