Ranking and Unranking Permutations in Linear Time

Wendy Myrvold, Department of Computer Science, University of Victoria, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

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: given an integer between 0 and n!-1, the value of the function is the permutation having this rank. We present simple ranking and unranking algorithms for permutations that can be computed using O(n) arithmetic operations.

The postscript file is 127,281 bytes, the dvi file is 19,732 bytes.
Please send me a note if you download a copy -- Thanks!
Appears in Information Processing Letters, 79 (2001) 281-284.
This message by George Russell appeared on the newsgroup sci.math.research in July 2001. It contains essentially the same algorithm developed in our paper, implemented in FORTRAN. He reports (private communication) that the algorithm was developed in 1993, but was never published.
The paper is referenced in Knuth volume 4, prefascicle 2B, Generating All Permutations.
Typo: On page 282 of the IPL version, in the second line the big-O expression should be O( (n log n)/(log log n) ).

Selected papers that refer to this paper:

Gustavo Rodrigues Galvao and Zanoni Dias, Computing rearrangement distance of every permutation in the symmetric group, Proceedings of the 2011 ACM Symposium on Applied Computing (SAC '11), (2011) 106-107.
Stefan Edelkamp, Damian Sulewski, and Cengizhan Yucel, Perfect Hashing for State Exploration on the GPU, Proceedings of the 20th Internation Conference on Automated Planning and Scheduling (ICAPS 2010), 57-64.
Daniel J. Ford, Encodings of cladograms and labeled trees Electronic Journal of Combinatorics, 17 (2010) 38 pages.
Sukriti Bhattacharya and Agostino Cortesi, A Distortion Free Watermark Framework for Relational Databases, 4th International Conference on Software and Data Technologies (ICSOFT 2009) 229-234.
Jose Antonio Pascual, Jose Antonio Lozano, and Jose Miguel Alonso, Parallelization of the Quadratic Assignment Problem on the Cell, XX Jornadas de Paralelismo. 16-18 Septiembre, A Coruñ.
Ting Kuo, A New Method for Generating Permutations in Lexicographic Order, Jounal of Science and Engineering Technology, 5 (2009) 21-29.
Richard E. Korf, Linear-time disk-based implicit graph search, Journal of the ACM (JACM), 55 (2008) ???-???.
Blai Bonet, Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order, Workshop on Search in Artificial Intelligence and Robotics at AAAI 2008.
Xiapu Luo, Edmond W. W. Chan, and Rocky K. C. Chang, Crafting Web Counters into Covert Channels, Proc. 22nd IFIP TC-11 International Information Security Conference (SEC’07), May 2007.
Ariel Felner, Richard E. Korf, Ram Meshulam and Robert C. Holte, Compressed Pattern Databases, Journal of Artificial Intelligence Research (JAIR), to appear, 2007.
Mark C. Wilson, Random and Exhaustive Generation of Permutations and Cycles, arXiv, math.CO/0702753.
Antti Valmari, What the small Rubik’s cube taught me about data structures, information theory, and randomisation, International Journal on Software Tools for Technology Transfer (STTT), Springer, 8 (2006) 180-194.
Stefan Edelkamp and Tilman Mehler, Incremental Hashing in State Space Search, 18th Workshop "New Results in Planning, Scheduling and Design" (PUK2004), Ulm, 24. September, 2004 (part of the 27th German Conference on Artificial Intelligence).
Roberto Grossi and Iwona Bialynicka-Birula, Rank-Sensitive Data Structures, String Processing and Information Retrieval (SPIRE 2005), Buenos Aires, November 2-4, 2005.
Richard E. Korf and Peter Schultze, Large-Scale Parallel Breadth-First Search, National Conference on Artificial Intelligence, AAAI-05, 1380-1385, July 2005.
Online Encyclopedia of Integer Sequences, Sequences A060117 and A060125 (submitted by Antti Karttunen).

Back to list of publications.