Lehmer code
The Lehmer code, also known as the inversion table or inversion vector, is a bijective encoding of a permutation \sigma \in S_n (the symmetric group on n elements) as a vector c_\sigma = (c_1, c_2, \dots, c_n) in the set C_n = \{0\} \times [0,1] \times [0,2] \times \cdots \times [0, n-1], where c_x = |\{ y : y < x, \sigma(y) > \sigma(x) \}| for each position x = 1, \dots, n, counting the number of larger values to the left of position x in the one-line notation of \sigma.[1] This representation uniquely maps each permutation to a sequence of non-negative integers satisfying $0 \leq c_x \leq x-1, with c_1 = 0 always, enabling efficient encoding and decoding in linear time O(n).[1] The code provides a natural way to order permutations lexicographically via the factorial number system, where the index of a permutation corresponds directly to the integer value of its Lehmer code interpreted in base factorials.[1] Named after the mathematician Derrick Henry "D. H." Lehmer (1905–1991), who described the code in detail in his 1960 paper "Teaching Combinatorial Tricks to a Computer" in the context of algorithmic generation of permutations,[2] the underlying inversion table concept has roots in 19th-century combinatorics but gained prominence through Lehmer's work, which emphasized its practical implementation for computer-based enumeration and analysis. In modern applications, the Lehmer code facilitates rank aggregation in machine learning, where it compresses partial rankings into vectors for efficient probabilistic modeling and optimization under metrics like Kendall tau distance.[1] It is also employed in permutation entropy calculations for time series analysis, enumerative coding for data compression, and generating uniform random permutations in algorithms, due to its prefix-free property and simplicity in decoding to the corresponding permutation via insertion of elements in decreasing order.[3] These properties make it a foundational tool in algebraic combinatorics, with extensions to weak orders, parabolic quotients, and even non-classical permutation structures like those in Coxeter groups.History and Definition
Historical Background
The Lehmer code traces its origins to the late 19th century, when French mathematician Charles-Ange Laisant introduced a factorial numbering system for representing permutations in his seminal paper. In this work, Laisant described a method to enumerate and encode permutations using factorial bases, providing a systematic way to assign unique indices to each permutation without employing the modern terminology of "Lehmer code." This innovation emerged within the broader context of enumerative combinatorics, where Laisant and contemporaries sought efficient tools for cataloging combinatorial objects during an era of growing interest in permutation theory.[4] The encoding was first proposed around 1906 by American mathematician Derrick Norman Lehmer and later elaborated in detail by his son, Derrick Henry Lehmer. The concept gained prominence in the mid-20th century through the efforts of Derrick Henry Lehmer, who adapted and popularized the encoding scheme for computational purposes. In his 1960 paper, Lehmer presented the code as a practical tool for generating and manipulating permutations on early computers, emphasizing its utility in combinatorial enumeration algorithms. This development reflected the era's shift toward computer-assisted mathematics, where Lehmer's expertise in numerical analysis and permutation generation addressed the need for efficient data structures in automated problem-solving.[5] Although the Lehmer code is named after Derrick Henry Lehmer, its foundational ideas bear resemblance to earlier notions like inversion tables, which served as precursors in permutation analysis. The code's evolution from Laisant's theoretical framework to the Lehmers' computational applications underscores its enduring role in bridging classical combinatorics with modern computing.Formal Definition
The Lehmer code of a permutation \sigma of the set = \{1, 2, \dots, n\} is the sequence L(\sigma) = (L(\sigma)_1, L(\sigma)_2, \dots, L(\sigma)_n), where each entry is defined as L(\sigma)_i = \bigl|\{j < i : \sigma(j) > \sigma(i)\}\bigr| for i = 1, 2, \dots, n.[1] This counts, for each position i, the number of elements to the left of i in the permutation that are larger than \sigma(i), providing a measure of the left-inversions involving the element at position i.[1] For example, consider the permutation \sigma = (3, 1, 4, 2) of {{grok:render&&&type=render_inline_citation&&&citation_id=4&&&citation_type=wikipedia}}.- For i=1, \sigma(1)=3; no elements to the left, so L(\sigma)_1 = 0.
- For i=2, \sigma(2)=1; the element to the left is $3 > 1 (one element), so L(\sigma)_2 = 1.
- For i=3, \sigma(3)=4; the elements to the left are $3 < 4 and $1 < 4 (zero elements larger), so L(\sigma)_3 = 0.
- For i=4, \sigma(4)=2; the elements to the left are $3 > 2, $1 < 2, $4 > 2 (two elements), so L(\sigma)_4 = 2.
Thus, L(\sigma) = (0, 1, 0, 2).[1]
Encoding and Decoding
Encoding a Permutation
To encode a permutation \sigma of n elements into its Lehmer code L(\sigma) = (L_1, L_2, \dots, L_n), where each L_i satisfies $0 \leq L_i \leq n - i, proceed sequentially from left to right, tracking the set of unused elements at each step. This process counts, for each position i, the number of unused elements smaller than \sigma(i) that have not yet appeared in the prefix \sigma(1) to \sigma(i-1). Equivalently, L_i is the number of elements to the right of position i that are smaller than \sigma(i), as the unused elements at step i consist precisely of \sigma(i) and the elements in positions i+1 to n.[3] The algorithm is as follows:- Initialize the set of available elements as S = \{1, 2, \dots, n\} (assuming the permutation is of the numbers 1 through n).
- For each position i from 1 to n:
- The resulting sequence (L_1, L_2, \dots, L_n) is the Lehmer code.
- Start with S = \{1,2,3,4,5,6,7\}. For i=1, \sigma(1)=2; smaller elements in S: 1 (count=1). Set L_1=1, remove 2; S=\{1,3,4,5,6,7\}.
- For i=2, \sigma(2)=6; smaller in S: 1,3,4,5 (count=4). Set L_2=4, remove 6; S=\{1,3,4,5,7\}.
- For i=3, \sigma(3)=1; smaller in S: none (count=0). Set L_3=0, remove 1; S=\{3,4,5,7\}.
- For i=4, \sigma(4)=7; smaller in S: 3,4,5 (count=3). Set L_4=3, remove 7; S=\{3,4,5\}.
- For i=5, \sigma(5)=4; smaller in S: 3 (count=1). Set L_5=1, remove 4; S=\{3,5\}.
- For i=6, \sigma(6)=5; smaller in S: 3 (count=1). Set L_6=1, remove 5; S=\{3\}.
- For i=7, \sigma(7)=3; smaller in S: none (count=0). Set L_7=0, remove 3; S=\emptyset.
Decoding a Lehmer Code
The Lehmer code establishes a bijection between the set of all permutations of n elements and the set of integer sequences L = (L_1, L_2, \dots, L_n) satisfying $0 \leq L_i \leq n - i for each i = 1, \dots, n.[6] Decoding reconstructs the unique permutation \sigma corresponding to L via an algorithm that operates in linear time O(n).[6] The algorithm begins with the set of available elements S = \{1, 2, \dots, n\}, sorted in increasing order. For each position i from 1 to n, it selects the (L_i + 1)-th smallest element from the current S as \sigma(i) and removes that element from S. This process builds \sigma from left to right, ensuring each choice respects the inversion counts encoded in L.[6] In detail, for each i, L_i specifies the number of smaller unused elements to skip before selecting the next one; the selected element is thus the one that would have exactly L_i remaining smaller elements placed after it in the permutation. This step-wise selection guarantees the bijection, as every valid L produces a unique \sigma and vice versa.[6] The decoding is the inverse of the encoding operation, which counts right inversions for each position.[6] Consider the example with n=7 and L = [1, 4, 0, 3, 1, 1, 0]. Start with S = \{1, 2, 3, 4, 5, 6, 7\}.- For i=1, L_1=1: Select the 2nd smallest in S (which is 2); set \sigma(1) = 2, update S = \{1, 3, 4, 5, 6, 7\}.
- For i=2, L_2=4: Select the 5th smallest in S (1, 3, 4, 5, 6 → 6); set \sigma(2) = 6, update S = \{1, 3, 4, 5, 7\}.
- For i=3, L_3=0: Select the 1st smallest in S (1); set \sigma(3) = 1, update S = \{3, 4, 5, 7\}.
- For i=4, L_4=3: Select the 4th smallest in S (3, 4, 5, 7 → 7); set \sigma(4) = 7, update S = \{3, 4, 5\}.
- For i=5, L_5=1: Select the 2nd smallest in S (3, 4 → 4); set \sigma(5) = 4, update S = \{3, 5\}.
- For i=6, L_6=1: Select the 2nd smallest in S (3, 5 → 5); set \sigma(6) = 5, update S = \{3\}.
- For i=7, L_7=0: Select the 1st smallest in S (3); set \sigma(7) = 3, update S = \emptyset.
Properties
Relation to the Factorial Number System
The Lehmer code provides a direct bijection between the set of all permutations of n elements, denoted S_n, and the integers in the range [0, n! - 1] through its interpretation as a representation in the factorial number system. This connection was introduced by Derrick Lehmer to facilitate computational enumeration of permutations by assigning each one a unique numerical index corresponding to its position in colexicographic order. The factorial number system, also known as the factoradic system, is a mixed radix numeral system where the place values are the factorials k! for positions indexed from the right starting at k=0, and each digit l_k satisfies $0 \leq l_k \leq k. This ensures every nonnegative integer up to n! has a unique representation without leading zeros beyond the necessary positions. For a permutation \sigma \in S_n, the reversed Lehmer code (c_n, c_{n-1}, \dots, c_1) (where c_x is as defined) uses digits that exactly fit these constraints, as the values count the inversions in a way that aligns with colex ordering from right to left.[7] The rank r(\sigma), or colexicographic index, is then computed as the value of this factoradic number: r(\sigma) = \sum_{k=1}^{n} c_k \cdot (k-1)! This formula maps each permutation uniquely to its ordinal position, starting from 0 for the identity permutation. For instance, with n=7 and Lehmer code c_\sigma = [0, 1, 1, 3, 0, 4, 1] (so reversed [1, 4, 0, 3, 1, 1, 0]), the rank is r(\sigma) = 0 \cdot 0! + 1 \cdot 1! + 1 \cdot 2! + 3 \cdot 3! + 0 \cdot 4! + 4 \cdot 5! + 1 \cdot 6! = 0 + 1 + 2 + 18 + 0 + 480 + 720 = 1221. This places \sigma as the 1222nd permutation (1-indexed) in colexicographic order among the $7! = 5040 total.[8] This numerical bijection enables efficient sorting and traversal of permutations by treating them as integers in the factorial base, which underpins algorithms for generating permutations in colexicographic sequence without redundant computations.Statistical Properties and Independence
When considering a uniformly random permutation \sigma of = \{1, 2, \dots, n\}, the components of its Lehmer code L(\sigma) = (L_1, L_2, \dots, L_n) exhibit notable probabilistic behavior. Specifically, each L_i is uniformly distributed over the set \{0, 1, \dots, i-1\}, and the L_i are mutually independent random variables.[9] This uniformity arises because, for each fixed i, the value L_i counts the number of elements to the left of position i that are larger than \sigma_i; since \sigma is random, \sigma_i is equally likely to be in any rank among the prefix \sigma_1, \dots, \sigma_i, yielding P(L_i = k) = 1/i for k = 0, 1, \dots, i-1. The independence follows from the fact that the relative ordering within each prefix is uniformly random and the counts decouple across positions due to the exchangeability of the permutation.[9] The sum \sum_{i=1}^n L_i equals the total number of inversions in \sigma, and under the uniform distribution, this sum has expected value n(n-1)/4. This expectation can be derived by linearity: each possible pair (j, k) with j < k forms an inversion with probability $1/2, and there are \binom{n}{2} such pairs. In the Lehmer code, the positions i where L_i = 0 precisely correspond to the left-to-right maxima of \sigma, as L_i = 0 means no element to the left of i is larger than \sigma_i. The number of left-to-right maxima is thus the count of such zeros in L(\sigma), while the number of right-to-left maxima can be expressed analogously using a suitable transformation of the code components.[9] The independence of the L_i under uniform random permutations enables efficient sampling and simulation techniques, facilitating Monte Carlo methods in modern combinatorics, such as learning distributions over permutation spaces in post-2020 computational studies.[9]Applications
Combinatorial Enumeration
Lehmer codes play a central role in combinatorial enumeration by enabling unranking, the process of generating the specific permutation corresponding to a given rank r in the range [0, n! - 1] under lexicographic order. The rank r is expressed in the factorial number system, yielding digits d_{n-1}, d_{n-2}, \dots, d_1 where $0 \leq d_k \leq k and r = \sum_{k=1}^{n-1} d_k \cdot k!. These digits form the Lehmer code, and decoding proceeds by successively selecting the d_k-th (0-based index) unused element from the remaining set \{1, 2, \dots, n\} to build the permutation.[10] This bijection ensures every rank maps uniquely to a permutation, facilitating direct access without generating preceding ones.[11] In applications, Lehmer codes support efficient algorithms for enumerating all permutations without duplicates or omissions, as successive unranking from ranks 0 to n! - 1 produces the complete lexicographic list. Historically, Derrick H. Lehmer incorporated these codes into mechanical computing devices, known as teaching machines, to solve combinatorial problems like permutation generation and counting, as detailed in his foundational work on machine tools for combinatorics.[12] Such methods allowed early digital and analog computers to tackle enumeration tasks that were otherwise infeasible by exhaustive search.[8] For illustration, consider n = 4 and rank r = 5 (0-based). The factorial representation is $5 = 0 \cdot 3! + 2 \cdot 2! + 1 \cdot 1! + 0 \cdot 0!, yielding Lehmer code digits (0, 2, 1, 0). Starting with the set \{1, 2, 3, 4\}:- Select the 0-th element: 1; remaining: \{2, 3, 4\}.
- Select the 2-nd element: 4; remaining: \{2, 3\}.
- Select the 1-st element: 3; remaining: \{2\}.
- Select the 0-th element: 2.
itertools.permutations introduced in version 2.6 (2008), efficient generation leverages lexicographic ordering akin to unranking techniques, enabling scalable enumeration for practical combinatorial tasks.[15][16] The independence of Lehmer code digits further supports uniform sampling in enumeration algorithms.[10]