Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order

Contents

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.