Improved Linear-Time Ranking of Permutations
Harold R. Parks, Dean C. Wills Β· Journal of Applied Mathematics and Computation Β· 2021
A ranking function for the permutations on ππ symbols assigns a unique integer in the range [0, ππ! -1] to each of the ππ!permutations.The corresponding unranking function is the inverse.We present simple ππ(ππ) ranking and unranking functions and permutation representations of a Foata transformation by Karttunen of the rankings introduced by Myrvold and Ruskey.Previous studies in the literature have either focused on lexicographic order, as the only reasonably intuitive order, or focused on the runtime performance of the algorithms.Our approach differs in that we provide an order that has algebraic significance while maintaining optimum performance.In addition, the methodology introduced herein, where mathematics and analysis are performed in the context of a descending transposition representation, is not only useful for analyzing and defining ranking, but also for the representation of all finite groups per Cayley's Theorem, which states that every group is isomorphic to a permutation group.Using this methodology, simple and efficient programs can be written to study and classify groups of different characteristics.