A CAT algorithm for generating permutations with a fixed number of inversions

DOI10.1016/S0020-0190(02)00481-7zbMath1173.68587MaRDI QIDQ1007583

Scott Effler, Frank Ruskey

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

algorithmspermutationindexinversionexhaustive listing

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05)

Related Items

Gray code for permutations with a fixed number of cycles ⋮ Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order ⋮ Restricted compositions and permutations: from old to new Gray codes ⋮ An efficient Gray code algorithm for generating all permutations with a given major index ⋮ A Constant Amortized Time Algorithm for Generating Left-Child Sequences in Lexicographic Order ⋮ From enumerating to generating: a linear time algorithm for generating 2D lattice paths with a given number of turns ⋮ Generating restricted classes of involutions, Bell and Stirling permutations ⋮ Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order ⋮ Algorithmic combinatorics based on slicing posets ⋮ More restrictive Gray codes for some classes of pattern avoiding permutations ⋮ Gray code for derangements

Cites Work

• Generating alternating permutations lexicographically
• Linear probing and graphs
• An asymptotic expansion for the number of permutations with a certain number of inversions
• A new algorithm for generating derangements
• Generating Linear Extensions Fast
• Unnamed Item
• Unnamed Item
• Unnamed Item