6533b7cffe1ef96bd12586e4
RESEARCH PRODUCT
Gray code for permutations with a fixed number of cycles
Jean-luc Barilsubject
Golomb–Dickman constantPolynomial codeRestricted permutationsGenerating algorithms0102 computer and information sciences02 engineering and technology01 natural sciencesTheoretical Computer ScienceGray codeCombinatoricsPermutation[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsTransposition arrayComputingMilieux_MISCELLANEOUSMathematicsDiscrete mathematicsSelf-synchronizing codeAmortized analysisMathematics::CombinatoricsParity of a permutation020206 networking & telecommunicationsGray codes010201 computation theory & mathematicsConstant-weight codeMathematicsofComputing_DISCRETEMATHEMATICSdescription
AbstractWe give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2007-06-01 |