Function Repository Resource:

LehmerCodeFromPermutation

Source Notebook

Create the Lehmer code corresponding to a given permutation

Contributed by: Ed Pegg Jr

ResourceFunction["LehmerCodeFromPermutation"][perm]

creates the Lehmer code corresponding to permutation perm.

Details and Options

The generating algorithm is as follows: For each number in the permutation, count how many subsequent values it exceeds.

Examples

Basic Examples (1) 

Generate the Lehmer code of a permutation:

In[1]:=
ResourceFunction[
 "LehmerCodeFromPermutation"][{1, 2, 9, 5, 4, 12, 7, 6, 3, 11, 10, 8}]
Out[1]=

Scope (1) 

Generate the Lehmer code for a particular permutation:

In[2]:=
ResourceFunction["LehmerCodeFromPermutation"][RandomSample[Range[60]]]
Out[2]=

Properties and Relations (2) 

Multiplying by factorials leads to the factorial number system representation or lexicographic index of the given permutation:

In[3]:=
Total[MapIndexed[#1 (#2[[1]] - 1)! &, Reverse[{0, 0, 6, 2, 1, 6, 2, 1, 0, 2, 1, 0}]]]
Out[3]=

The lexicographic index of a permutation works as expected:

In[4]:=
Table[Total[
  MapIndexed[#1 (#2[[1]] - 1)! &, Reverse[ResourceFunction["LehmerCodeFromPermutation"][
     Permutations[Range[4]][[n]]]]]], {n, 1, 24}]
Out[4]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Version History

  • 2.0.0 – 20 December 2019
  • 1.0.0 – 25 January 2019

Related Resources

License Information