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) 281284.

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 bigO 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) 106107.

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), 5764.

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) 229234.

Jose Antonio Pascual, Jose Antonio Lozano, and Jose Miguel Alonso,
Parallelization of the Quadratic Assignment Problem on the Cell,
XX Jornadas de Paralelismo. 1618 Septiembre, A Coruń.

Ting Kuo,
A New Method for Generating Permutations in Lexicographic Order,
Jounal of Science and Engineering Technology, 5 (2009) 2129.

Richard E. Korf,
Lineartime diskbased 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 TC11 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) 180194.

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 BialynickaBirula,
RankSensitive Data Structures,
String Processing and Information Retrieval (SPIRE 2005),
Buenos Aires, November 24, 2005.

Richard E. Korf and Peter Schultze,
LargeScale Parallel BreadthFirst Search,
National Conference on Artificial Intelligence, AAAI05, 13801385,
July 2005.

Online Encyclopedia of Integer Sequences,
Sequences A060117 and A060125 (submitted by Antti Karttunen).
Back to list of publications.