𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A loopless algorithm for generating the permutations of a multiset

✍ Scribed by Vincent Vajnovszki

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
372 KB
Volume
307
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.

πŸ“œ SIMILAR VOLUMES

A CAT algorithm for generating permutati
A CAT algorithm for generating permutations with a fixed number of inversions
✍ Scott Effler; Frank Ruskey πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 103 KB

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.

A Cost-Optimal Pipeline Algorithm for Pe
A Cost-Optimal Pipeline Algorithm for Permutation Generation in Lexicographic Order
✍ ClΓ©mentin Tayou Djamegni; Maurice TchuentΓ© πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 142 KB

In this paper we solve the open problem of designing a costoptimal parallel algorithm for generating permutations of M elements out of the set {0, 1, . . . , N -1}, in lexicographic order. Our algorithm runs on the simplest model of parallel computation, i.e., a linear array of size M, where each pr