# Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms

arXiv: https://arxiv.org/abs/2511.19089 · HTML: https://mlsanity.com/paper/2511.19089/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Linear Ordering Problem: Time for a Change](https://mlsanity.com/paper/2605.31051/) (2026)

## Abstract (arXiv)

A suitable choice of the representation of candidate solutions is crucial for the efficiency of evolutionary algorithms and related metaheuristics. We focus on problems in permutation spaces, which are at the core of numerous practical applications of such algorithms, e.g. in scheduling and transportation. Inversion vectors (also called Lehmer codes) are an alternative representation of the permutation space Sn compared to the classical encoding as a vector of n unique entries. In particular, they do not require any constraint handling. Using rigorous mathematical runtime analyses, we compare the efficiency of inversion vector encodings to the classical representation and give theory-guided advice on their choice. Moreover, we link the effect of local changes in the inversion code space to classical measures on permutations like the number of inversions. Finally, through experimental studies on linear ordering and quadratic assignment problems, we demonstrate the practical efficiency of inversion vector encodings.