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

DOI10.1016/J.JDA.2014.01.001zbMATH Open1298.05012arXiv1302.6558OpenAlexW1988055946MaRDI QIDQ2447540FDOQ2447540

Authors: Vincent Vajnovszki 

Publication date: 28 April 2014

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

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.

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

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

zbMATH Keywords

major index(bounded) compositions of an integergenerating algorithms permutations

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A new Euler-Mahonian constructive bijection
• Restricted compositions and permutations: from old to new Gray codes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A CAT algorithm for generating permutations with a fixed number of inversions

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)