𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Scott Effler; Frank Ruskey

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
103 KB
Volume
86
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

A loopless algorithm for generating the
A loopless algorithm for generating the permutations of a multiset
✍ Vincent Vajnovszki πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 372 KB

Many combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shu e on trajectories (deΓΏned previou

A fast algorithm for the inversion of ge
A fast algorithm for the inversion of general Toeplitz matrices
✍ P.G. Martinsson; V. Rokhlin; M. Tygert πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 590 KB

we propose a "fast" algorithm for the construction of a data-sparse inver'~ of a general Toeplitz matrix. The computational cost for inverting an N Γ— N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(Nlog2N) cost of previously published