A CAT Algorithm for Generating Permutations with a Fixed Number of Inversions

Scott Effler, Department of Computer Science, University of Victoria, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

Abstract:

We develop a constant amortized time (CAT) algorithm for generating permutations with a given number of inversions. We also develop an algorithm for the generation of permutations with given index.

Keywords: Permutation, exhaustive listing, inversion, index.

The postscript file is 342499 bytes, the dvi file is 35892 bytes, the pdf file is 164414 bytes.
Appears in Information Processing Letters, 86/2 (2003) 107-112.
The algorithms are implemented and can be seen in action on the Combinatorial Object Server at the page http://www.theory.csc.uvic.ca/~cos/gen/perm.html .

Selected Citations:

James Korsh and Paul LaFollette, A Loopless Gray Code for Rooted Trees, ACM Transactions on Algorithms, 2 (2006) 135--152.
Miklós Bóna, Combinatorics of Permutations, Chapman & Hall/CRC, 2003.
Vijay K. Garg, Algorithmic Combinatorics Based on Slicing Posets, FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science: 22nd Conference Kanpur, India, December 12-14, 2002. Lecture Notes in Computer Science #2556, pp.169-181.

Back to list of Frank Ruskey's publications.