An efficient Gray code algorithm for generating all permutations with a given major index

DOI10.1016/J.JDA.2014.01.001MaRDI QIDQ2447540zbMATH OpenOpenAlexFDO

Authors Vincent Vajnovszki

Publication date 28 April 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.6558

zbMATH Keywords

(bounded) compositions of an integergenerating algorithms permutationsmajor index

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05)

Abstract: In [S. Effler, F. Ruskey, A CAT algorithm for listing permutations with a given number of inversions, {it I.P.L.}, 86/2 (2003)] the authors give an algorithm, which appears to be CAT, for generating permutations with a given major index. In the present paper we give a new algorithm for generating a Gray code for subexcedant sequences. We show that this algorithm is CAT and derive it into a CAT generating algorithm for permutations with a given major index.

Recommendations

• scientific article; zbMATH DE number 5855074
• A Gray code for permutations of size 2d with d descents
• Gray code for permutations with a fixed number of cycles
• Gray code for permutations with a fixed number of left-to-right minima.
• More restrictive Gray codes for some classes of pattern avoiding permutations

Cites work

• A CAT algorithm for generating permutations with a fixed number of inversions
• A new Euler-Mahonian constructive bijection
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 553907 (Why is no real title available?)
• scientific article; zbMATH DE number 1506516 (Why is no real title available?)
• Restricted compositions and permutations: from old to new Gray codes

Cited in

(2)

• A Gray code for permutations of size 2d with d descents
• A loopless implementation of a gray code for signed permutations

This page was built for publication: An efficient Gray code algorithm for generating all permutations with a given major index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447540)