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.
Selected Citations:

James Korsh and Paul LaFollette,
A Loopless Gray Code for Rooted Trees,
ACM Transactions on Algorithms, 2 (2006) 135152.

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 1214, 2002.
Lecture Notes in Computer Science #2556, pp.169181.
Back to list of Frank Ruskey's publications.