Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order

Bonet Blai

We present uniform and non-uniform algorithms to rank and unrank permutations in lexicographic order. The uniform algorithms run in O(n log n) time and outperform Knuth's ranking algorithm in all the experiments, and also the linear-time non-lexicographic algorithm of Myrvold-Ruskey for permutations up to size 128. The non-uniform algorithms generalize Korf-Schultze's linear time algorithm yet require much less space.

Subjects: 15. Problem Solving; 15.7 Search

Submitted: May 6, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.