A Unified View of Bijective Transformations for Optimizing Permutation Problems

Many optimization algorithms represent solutions as permutations. However, despite their apparent simplicity, permutations pose significant challenges - especially for Global Random Search (GRS) algorithms - due to the mutual-exclusivity constraint. This constraint complicates both the learning and sampling of probability distributions over the permutation space, often leading to computationally expensive procedures. A promising alternative involves transforming permutation-encoded solutions into integer vectors using bijective functions on the symmetric group Sn, resulting in what are known as inversion vectors. While inversion vectors have been studied for centuries, a unified and formal framework encompassing all their codifications has been lacking. In this paper, we introduce precise definitions and a unified notation for various types of inversion vector codifications. We establish bijective transformations between them, providing a formal characterization of their relationships and properties. Leveraging this theoretical foundation, we analyze and explain the behavior of GRS algorithms across different permutation problems when using different inversion vector representations.