Harold R. Parks1, Dean C. Wills2,*
1Department of Mathematics, Oregon State University, Corvallis, Oregon, USA.
2AppDynamics, San Francisco, California, USA.
*Corresponding author: Dean C. Wills
Abstract
A ranking function for the permutations on n symbols assigns a unique integer in the range [0,n! -1] to each of the n! permutations. The corresponding unranking function is the inverse. We present simple O(n) 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.
References
[1] The OEIS Foundation Inc. (2001). The On-Line Encyclopedia of Integer Sequences. [Online]. Available: https://oeis.org/A060117.
[2] W. Myrvold and F. Ruskey. (2001). “Ranking and unranking permutations in linear time.” Inf. Process. Lett., vol. 79, no. 6, pp. 281-284, Sep. 2001.
[3] D. C. Wills. (2009). “Connections between combinatorics of permutations and algorithms and geometry”. Ph.D. dissertation, Oregon State University, Corvallis, OR, USA, 2009, aAI3376756.
[4] D. Foata and M. Schützenberger. (1970). Théorie géométrique des polynômes Eulériens, ser. Lecture notes in mathematics. Springer, 1970.
[5] D. E. Knuth. (1997). The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1997.
[6] A. Genitrini and M. Pepin. (2021). “Lexicographic unranking of combinations revisited.” Algorithms, vol. 14, no. 3, p. 97, Mar 2021. [Online]. Available: http://dx.doi.org/10.
[7] P. Hartman and J. Sawada. (2019). “Ranking and unranking fixed-density necklaces and Lyndon words,” Theoret. Comput. Sci., vol. 791, pp. 36-47, 2019.
[8] M. Mareš and M. Straka. (2007). “Linear-time ranking of permutations,” in Algorithms – ESA 2007, ser. Lecture Notes in Computer Science, W. E. Arge L., Hoffmann M., Ed. Springer, Berlin, Heidelberg, 2007, vol. 4698, pp. 187-193.
[9] J. Meier. (2008). Groups, Graphs and Trees: An Introduction to the Geometry of Infinite Groups, ser. London Ma-thematical Society Student Texts. Cambridge University Press, 2008.
How to cite this paper
Improved Linear-Time Ranking of Permutations
How to cite this paper: Harold R. Parks, Dean C. Wills. (2021) Improved Linear-Time Ranking of Permutations. Journal of Applied Mathematics and Computation, 5(4), 277-282.
DOI: https://dx.doi.org/10.26855/jamc.2021.12.006